// flatten example from 'Static Determination of Quantitative Resource Usage for Higher-Order Programs' by Jost et. al. module DfsFlatten; data Tree<A> = Leaf(A) | Node(Tree<A>,Tree<A>); def List<A> cons<A>(A x, List<A> xs) = Cons(x,xs) ; // let rec dfsAcc g t acc = // match t with // | Leaf(x) -> g x acc // | Node(t1,t2) -> dfsAcc g t2 (dfsAcc g t1 acc) // ;; def List<A> dfsAcc<A>(g)(Tree<A> t, List<A> acc) = case t { Leaf(x) => g(x,acc); Node(t1,t2) => dfsAcc(t2,dfsAcc(t1,acc)); }; // let rec revApp l acc = // match l with // | Nil -> acc // | Cons(y,ys) -> revApp ys (Cons(y,acc)) // ;; def List<A> revApp<A>(List<A> l, List<A> acc) = case l { Nil => acc; Cons(y,ys) => revApp(ys, Cons(y,acc)); }; def List<A> flatten<A>(Tree<A> t) = revApp(dfsAcc(cons)(t, Nil), Nil); def List<A> start<A>(Tree<A> t) = flatten(t); { // Main }