[memoize] General memoization function #algorithm

memoize.ml

let memoize ?(size = 100) f =
  let tbl = Hashtbl.create size in
  let rec g = fun x ->
    try Hashtbl.find tbl x
    with Not_found ->
      let v = f g x in
      Hashtbl.add tbl x v;
      v
  in
  f g

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

let fib_mem = memoize fib

let _ =
  print_int (fib_mem 50);
  print_newline ()