Catamorphism (generalised fold on type)

// Catamorphism
// Generalised Fold on a datatype

type exp = | Var of string
           | Lambda of string * exp
           | Apply of exp * exp

// This fold was made Tail Recursive using continuations.
let foldExpr varF lamF appF exp =
  let rec Loop e cont =
      match e with
      | Var x -> cont (varF x)
      | Lambda (x, body) -> Loop body (fun bodyAcc -> cont (lamF x bodyAcc))
      | Apply (l, r) -> Loop l (fun lAcc ->
                        Loop r (fun rAcc ->
                              cont (appF lAcc rAcc)))
  Loop exp (fun x -> x)


let toString =
  foldExpr
      (fun x -> sprintf "%s" x)
      (fun x y -> sprintf "(λ%s.%s)" x y)
      (fun x y -> sprintf "(%s %s)" x y)

printf "%s" (toString (Apply(Lambda("x", Var "x"), Lambda("y", Var "y"))))