// 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

}