egison-5.0.0: sample/tree.egi

def tree {a, b} (a: Matcher b) : Matcher (Tree b) := matcher
  | leaf $ as a with
    | Leaf $x -> [x]
    | Node _ _ -> []
  | node $ $ as (a, multiset (tree a)) with
    | Leaf _ -> []
    | Node $x $ts -> [(x, ts)]
  | $ :: $ as (a, tree a) with
    | Leaf _ -> []
    | Node $x $ts -> map (\t -> (x, t)) ts
  | $ ++ $ as (list a, tree a) with
    | $tgt -> matchAll tgt as tree a with
              | loop $i (1, $n) ($x_i :: ...) $t
                -> (map (\i -> x_i) [1..n], t)
  | $ as something with
    | $tgt -> [tgt]

def treeData : Tree String :=
  Node "Programming language"
    [Node "pattern-match-oriented" [Leaf "Egison"],
     Node "Functional language"
       [Node "Strictly typed" [Leaf "OCaml", Leaf "Haskell", Leaf "Curry", Leaf "Coq"],
        Node "Dynamically typed" [Leaf "Egison", Leaf "Lisp", Leaf "Scheme", Leaf "Racket"]],
     Node "Logic programming" [Leaf "Prolog", Leaf "Curry"],
     Node "Object oriented" [Leaf "C++", Leaf "Java", Leaf "Ruby", Leaf "Python", Leaf "OCaml"]]

def ancestors {Eq a} (x: a) (t: Tree a) : [[a]] :=
  matchAllDFS t as tree eq with
    | $hs ++ leaf #x -> hs

assertEqual "ancestors"
  (ancestors "Egison" treeData)
  [["Programming language", "pattern-match-oriented"], ["Programming language", "Functional language", "Dynamically typed"]]

def descendants {Eq a} (x: a) (t: Tree a) : [a] :=
  matchAllDFS t as tree eq with
    | _ ++ #x :: _ ++ leaf $y -> y

assertEqual "descendants"
  (descendants "Functional language" treeData)
  ["OCaml", "Haskell", "Curry", "Coq", "Egison", "Lisp", "Scheme", "Racket"]