Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
39 lines (35 sloc) 845 Bytes
let time f =
let start = Time.now () in
let x = f () in
let stop = Time.now () in
printf "Time: %s\n" (Time.Span.to_string (Time.diff stop start));
x ;;
let memoize f =
let table = Hashtbl.Poly.create () in
(fun x ->
match Hashtbl.find table x with
| Some y -> y
| None ->
let y = f x in
Hashtbl.add_exn table ~key:x ~data:y;
y
);;
#part 1
let memo_rec f_norec =
let rec f = memoize (fun x -> f_norec f x) in
f
;;
#part 2
let rec x = lazy (Lazy.force x + 1);;
#part 3
Lazy.force x;;
#part 4
let fib_norec fib i =
if i <= 1 then i
else fib (i - 1) + fib (i - 2) ;;
#part 5
let lazy_memo_rec f_norec x =
let rec f = lazy (memoize (fun x -> f_norec (Lazy.force f) x)) in
(Lazy.force f) x
;;
time (fun () -> lazy_memo_rec fib_norec 40);;