memo.fs

open System.Collections.Generic;

let memoize f = 
  let table = new Dictionary<_, _>()
  fun k ->
     if lock table (fun () -> table.ContainsKey(k))
     then 
       lock table (fun () -> table.[k])
     else 
       let res = f k
       let out = lock table (fun () -> table.[k] <- res; res)
       out
       
let memoize_rec f = 
  let table = new Dictionary<_, _>()
  let memod = ref None;
  let ff = fun k ->
     if lock table (fun () -> table.ContainsKey(k))
     then 
       lock table (fun () -> table.[k])
     else 
       let res = f k (!memod).Value
       ignore (lock table (fun () -> table.[k] <- res))
       res
  
  memod := Some(ff)
  (!memod).Value
  
       
let f x = 
  printfn "hi"
  x
  
let f_memo = memoize f 

ignore (f_memo 5)
ignore (f_memo 5)

let fib x recurse = 
  if x = 0 || x = 1
  then x 
  else (recurse (x - 1)) + (recurse (x - 2))
  
let fib_memo = memoize_rec fib

printfn "%d" (fib_memo 30)