Skip to content

Instantly share code, notes, and snippets.

@fogus
Forked from rapha/trampoline.ml
Created September 17, 2011 23:52
Show Gist options
  • Save fogus/1224507 to your computer and use it in GitHub Desktop.
Save fogus/1224507 to your computer and use it in GitHub Desktop.
Trampolining in OCaml
(* 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);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment