memo.fs

open System
open System.Collections.Generic

let memoize_rec (f : ('a -> 'b) -> 'a -> 'b) =
  let m = Dictionary<'a, 'b> () in
  let rec g x =
    try
      m.[x]
    with
      | :? KeyNotFoundException ->
        let y = f g x in
          m.Add(x, y);
          y
  in
    g

let rec fib_n = function
    0 -> 0
  | 1 -> 1
  | n -> fib_n (n - 1) + fib_n (n - 2)

let rec fib_s self = function
    0 -> 0
  | 1 -> 1
  | n -> self (n - 1) + self (n - 2)

let fib_memo = memoize_rec fib_s

printfn "Naive."
print_duration (fun () -> fib_n 40) |> printfn "%i"
// Elapsed Time: 5900[ms]

printfn "Memoized."
print_duration (fun () -> fib_memo 40) |> printfn "%i"
// Elapsed Time: 5[ms]