sort.ml

let nil = { isEmpty = true } in
let cons = fun hd tl -> { isEmpty = false; head = hd; tail = tl } in
let rec foldrList = fun f z xs ->
  if xs.isEmpty then
    z
  else
    f xs.head (foldrList f z xs.tail)
in
let rec foldlList = fun f z xs ->
  if xs.isEmpty then
    z
  else
    foldlList f (f z xs.head) xs.tail
in
let read = foldlList (fun n d -> 10*n+d) 0 in
let empty = { isEmpty = true } in
let node = fun l x r -> { isEmpty = false; left = l; value = x; right = r } in
let leaf = fun x -> node empty x empty in
let rec foldrTree = fun f z t ->
  if t.isEmpty then
    z
  else
    foldrTree f (f t.value (foldrTree f z t.right)) t.left
in
let treeToList = foldrTree cons nil in
let exTree = node (leaf 1) 2 (leaf 3) in
read (treeToList exTree)