Dynamic Programming

fibは末尾再帰にすると高速になるという説明は、どこか論点がはずれているような気がする。いや、まちがっちゃいないんだけどさ。

さて、DPといえばボトムアップに計算するのが通例のよう（なの？）だが、どちらかというとトップダウンに計算して、キャッシュさせた方が見通しがよくて好きなのだ。いわゆる、Haskellのあれか？　なんか先日Schemerに聞いたら、なんかそれは違うとか何とかいってたような、なんだったっけか。
てなわけで、参照透過な任意の再帰関数をDP化させるための関数を作ってみる。

let cached n f =
  let cache = Array.make n None in
  let rec f' x =
    let i = Hashtbl.hash x mod n in
    match cache.(i) with
    | Some (w, y) when w = x -> y (* hit *)
    | _ -> begin (* miss *)
        let y = f f' x in
        cache.(i) <- Some (x, y);
        y
      end in
  f'

let fib f x =
  if x <= 1 then 1
  else f (x - 1) + f (x - 2)

let rec normal_fib x = fib normal_fib x

let dp_fib = cached 100 fib

cachedにキャッシュサイズと関数を渡すと、DP化した関数が返ってくる寸法。うまく再帰させること考えると、fibに再帰の時に使う関数を渡さなくてはならなくて、変な感じになってしまう。イマイチ。