cps vs non cps

cps.fs

module Tour.Functions


type tree = Leaf | Node of tree * tree

let rec make depth =
  if depth <= 0 then Leaf
  else
    let r = make (depth - 1) in
    let l = if depth % 100000 = 0 then r else Leaf in
    Node (r, l)

let size root =
  let rec helper tree =
    match tree with Leaf -> 0 | Node (l, r) -> helper l + helper r + 1
  in
  helper root

let size_tail root =
  let rec helper tree k =
    match tree with
    | Leaf -> k 0
    | Node (l, r) ->
        (helper ) l (fun sl ->
            (helper ) r (fun sr -> k (sl + sr + 1)))
  in
  helper root (fun n -> n)

let main =
  let n = 100000 in
  printf "Tree: depth = %d, size = %d\n" n (size (make n));

  (* Gives stack overflow *)
  (* Format.printf "Tree: depth = %d, size_tail = %d\n%!" n (size (make n)); *)
  (* WTF it gives stack overflow? *)
  (* Format.printf "Tree: depth = %d, size_tail = %d\n%!" n (size_tail (make n)); *)
  (* let n = 1000000 / 10 in *)
  printf "loop\n";
  for n = 1 to 1000 do
    let i = n * 10_00 in
    printf "Tree: depth = %d, size_tail      = %d\n" i
      (size_tail (make i));
    printf "Tree: depth = %d, size           = %d\n" i (size (make i))
  done;
  ()