tailcall.ml

(*
$ ocamlopt tail.ml
$ ./a.out 100000
length (tail call) executed in 0.000256s
length (while loop) executed in 0.000366s
length (recursive) executed in 0.001092s
$ ./a.out 100000000
length (tail call) executed in 0.255737s
length (while loop) executed in 0.272046s
length (recursive) died
*)
let rec length_rec = function
| [] -> 0
| _::xs' -> length_rec xs' + 1

let length_tailcall xs =
  let rec loop acc = function
  | [] -> acc
  | _::xs' -> loop (acc + 1) xs'
in loop 0 xs

let length_while xs =
  let len = ref 0 in
  let xs = ref xs in
  while !xs <> [] do
    len := !len + 1;
    xs := List.tl !xs
  done;
  !len

let time lbl f x =
  let t = Sys.time() in
  try
    let _ = f x in
    Printf.printf "%s executed in %fs\n%!" lbl (Sys.time() -. t)
  with _ -> Printf.printf "%s died\n%!" lbl

let () =
  let n = Sys.argv.(1) |> int_of_string in
  let xs = List.init n (fun x -> x) in
  time "length (tail call)" length_tailcall xs;
  time "length (while loop)" length_while xs;
  time "length (recursive)" length_rec xs