Trampolining in OCaml

trampoline.ml

(* translated from http://blog.richdougherty.com/2009/04/tail-calls-tailrec-and-trampolines.html *)

(* implement trampolining *)
type 'a bounce = Done of 'a | Call of (unit -> 'a bounce)

let rec trampoline = function
  | Call thunk -> trampoline (thunk())
  | Done x     -> x

(* define some functions which use them *)
let rec
  even n = if n = 0 then (Done true) else (Call (fun () -> odd (n-1)))
and
  odd n = if n = 0 then (Done false) else (Call (fun () -> even (n-1)))

(* test them out *)
let _ = 
  assert (trampoline (even 0) = true );
  assert (trampoline (even 1) = false);
  assert (trampoline (even 2) = true );
  assert (trampoline (even 3) = false);

  assert (trampoline (odd 0) = false);
  assert (trampoline (odd 1) = true);
  assert (trampoline (odd 2) = false);
  assert (trampoline (odd 3) = true);