F#でメモ化（ConditionalWeakTable）

F#

プログラムの高速化のため、一度計算した値を再利用することはしばしばあります。

しかし結果を状態として保存する必要があるため、F#では少し扱いにくいです。

そこで、ある関数を結果を再利用する関数に変換する、memoize関数を定義してみたいと思います。

memoize関数

入力と結果をDictionaryに保存しておく関数に変換しています。

またConditionalWeakTableを利用することにより、selectKeyで寿命を共にするオブジェクトを指定できるようになっています。

let memoize (f : 'Args -> 'Result) (selectKey : 'Args -> 'Key) = 
    let table = ConditionalWeakTable<'Key, Dictionary<'Args, 'Result>>()
    fun (args : 'Args) ->
        let key = selectKey args
        let dictionary = table.GetOrCreateValue(key)
        if dictionary.ContainsKey(args) = false then
            dictionary.[args] <- f args
        dictionary.[args]

利用しやすいように、複数入力に対応した関数を用意しておきます。（寿命は第一引数と同じになります。）

let memoize1 (f : 'Arg -> 'Result) =
    memoize f id

let memoize2 (f : 'Arg1 -> 'Arg2 -> 'Result) =
    let tupled = memoize (fun (x1, x2) -> f x1 x2) fst
    fun x1 x2 -> tupled (x1, x2)

let memoize3 (f : 'Arg1 -> 'Arg2 -> 'Arg3 -> 'Result) =
    let tupled = memoize (fun (x1, x2, x3) -> f x1 x2 x3) (fun (x, _, _) -> x)
    fun x1 x2 x3 -> tupled (x1, x2, x3)


実際の利用

下記のようなNameレコードを例にしてみます。

フルネームを作成するfull関数は、二度目以降は結果を再利用しています。

また計算結果はNameオブジェクトと寿命が同じになります。

type Name =
    { First : string
      Last : string
    }
module Name =
    let full = memoize1 (fun name -> 
        printf "called\n" 
        name.First + name.Last)

let name = { First = "John"; Last = "Smith" }
let full = Name.full name // called
let full2 = Name.full name


入力に参照型がない場合

今回はConditionalWeakTableを利用したため、寿命を共にする参照型の入力が必要となります。

寿命がなく、入力と結果が共にサイズが小さいのであれば、Dictionaryで管理してもいいと思われます。