(hatena (diary ’Nobuhisa)) このページをアンテナに追加 RSSフィード Twitter

10/12/27 : ぼくアルバイトぉぉぉ!!

[]めもりんこ

ゼクルッシュさん*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) //201115日 修正
let memoize2 f = memo curry2 uncurry2 f
let memoize3 f = memo curry3 uncurry3 f

人間それぞれ個性を持っていますから、人と人とを比較することはできませんし、そんなことに意味はありません。

でもF#のタプルは比較することができます!

(1, 2) = (1, 2) は true です。

というわけで Dictionary<int * int, int> のような表現も可能となります(when 'Key : equality を満たす)。

そのトリックを使ったのが上記のコード。

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

zeclzecl 2010/12/28 01:18 なんという魔法的メモ化だ、ふつくしすぎる…。
さすがはノブー・ポッター!勉強になります。

C#タプルは非常に残念な感じになっていますよね。
F#由来なのだから、同じように機能してほしかったっす。

NobuhisaNobuhisa 2010/12/29 22:02 ハリポタは1作目しか見てないノブー・ポッターです。
お役に立ててよかったです!きゅぴーん!

仕様的にF#ライクなタプルは難しそうですね。
ライブラリでの提供となるとあれが限界かなぁ。。。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証