めもりんこ
ゼクルッシュさん*1が「メモ化」について面白い記事を書かれていました。
メモ〜化したりスマス。 Memoization and Tail Recursive Function - Bug Catharsis
ぼくならこう書く!というのを少し考えてみました。
最初はコメント欄に投稿しようかと思ったのですが、はてなのコメント欄は半角スペースが削除されちゃうので・・・。
open System open System.Collections.Generic let create<'Key, 'Value when 'Key : equality> () = Dictionary<'Key, 'Value> () let memoize f = let dic = create () fun x -> if not (dic.ContainsKey(x)) then dic.Add(x, f x) dic.[x] let curry2 f x y = f (x, y) let curry3 f x y z = f (x, y, z) let uncurry2 f (x, y) = f x y let uncurry3 f (x, y, z) = f x y z let memo curry uncurry f = let m = memoize (uncurry f) in curry m let memoize0 f = let m = lazy f () in (fun () -> m.Value) //2011年1月5日 修正 let memoize2 f = memo curry2 uncurry2 f let memoize3 f = memo curry3 uncurry3 f
人間それぞれ個性を持っていますから、人と人とを比較することはできませんし、そんなことに意味はありません。
でもF#のタプルは比較することができます!
(1, 2) = (1, 2) は true です。
というわけで Dictionary
そのトリックを使ったのが上記のコード。
memoize0はちょっと卑怯ですが、卑怯なくらいが丁度いい。(え?)←改良しました!
一応実行例も載せておきます。(対話環境):
> let f0 () = printfn "I'm f0 !" ; 0 ;;
val f0 : unit -> int> let f0' = memoize0 f0 ;;
val f0' : (unit -> int)> f0' (), f0' ();;
I'm f0 !
val it : int * int = (0, 0)
> let f1 x = printfn "I'm f1 !" ; x + 1 ;;
val f1 : int -> int> let f1' = memoize f1 ;;
val f1' : (int -> int)> f1' 9, f1' 9 ;;
I'm f1 !
val it : int * int = (10, 10)
> let f2 x y = printfn "I'm f2 !" ; x + y ;;
val f2 : int -> int -> int> let f2' = memoize2 f2 ;;
val f2' : (int -> int -> int)> f2' 2 8, f2' 2 8 ;;
I'm f2 !
val it : int * int = (10, 10)
> let f3 x y z = printfn "I'm f3 !" ; x + y + z ;;
val f3 : int -> int -> int -> int> let f3' = memoize3 f3 ;;
val f3' : (int -> int -> int -> int)> f3' 2 3 5, f3' 2 3 5 ;;
I'm f3 !
val it : int * int = (10, 10)> f3' 3 2 5 ;; //順番を変えると・・・
I'm f3 !
val it : int = 10