これを行うためのより簡単な方法があるかどうかはわかりませんが、1 つのアプローチは、メモ化する y コンビネーターを作成することです。
let memoY f =
let cache = Dictionary<_,_>()
let rec fn x =
match cache.TryGetValue(x) with
| true,y -> y
| _ -> let v = f fn x
cache.Add(x,v)
v
fn
次に、再帰的に呼び出す関数を表す最初の引数を使用して、「let rec」の代わりにこのコンビネータを使用できます。
let tailRecFact =
let factHelper fact (x, res) =
printfn "%i,%i" x res
if x = 0 then res
else fact (x-1, x*res)
let memoized = memoY factHelper
fun x -> memoized (x,1)
編集
Mitya が指摘したように、メモmemoYの末尾再帰プロパティは保持されません。これは、例外と変更可能な状態を使用して、スタックをオーバーフローすることなく再帰関数をメモ化する改訂されたコンビネータです (元の関数自体が末尾再帰ではない場合でも!)。
let memoY f =
let cache = Dictionary<_,_>()
fun x ->
let l = ResizeArray([x])
while l.Count <> 0 do
let v = l.[l.Count - 1]
if cache.ContainsKey(v) then l.RemoveAt(l.Count - 1)
else
try
cache.[v] <- f (fun x ->
if cache.ContainsKey(x) then cache.[x]
else
l.Add(x)
failwith "Need to recurse") v
with _ -> ()
cache.[x]
残念ながら、各再帰呼び出しに挿入される機構はやや重いため、深い再帰を必要とするメモ化されていない入力のパフォーマンスは少し遅くなる可能性があります。ただし、他のいくつかのソリューションと比較して、これには、再帰関数の自然な表現への変更がかなり最小限で済むという利点があります。
let fib = memoY (fun fib n ->
printfn "%i" n;
if n <= 1 then n
else (fib (n-1)) + (fib (n-2)))
let _ = fib 5000
編集
これが他のソリューションとどのように比較されるかについて少し詳しく説明します。この手法は、例外がサイド チャネルを提供するという事実を利用しています。 type の関数は、'a -> 'b実際には type の値を返す必要はありませんが'b、代わりに例外を介して終了できます。戻り値の型に失敗を示す追加の値が明示的に含まれている場合は、例外を使用する必要はありません。もちろん、'b optionこの目的のために関数の戻り値の型として を使用できます。これは、次のメモ化コンビネータにつながります。
let memoO f =
let cache = Dictionary<_,_>()
fun x ->
let l = ResizeArray([x])
while l.Count <> 0 do
let v = l.[l.Count - 1]
if cache.ContainsKey v then l.RemoveAt(l.Count - 1)
else
match f(fun x -> if cache.ContainsKey x then Some(cache.[x]) else l.Add(x); None) v with
| Some(r) -> cache.[v] <- r;
| None -> ()
cache.[x]
以前は、メモ化プロセスは次のようでした。
fun fib n ->
printfn "%i" n;
if n <= 1 then n
else (fib (n-1)) + (fib (n-2))
|> memoY
ここで、 がではなく をfib返すという事実を組み込む必要があります。型に適したワークフローを考えると、これは次のように記述できます。int optionintoption
fun fib n -> option {
printfn "%i" n
if n <= 1 then return n
else
let! x = fib (n-1)
let! y = fib (n-2)
return x + y
} |> memoO
ただし、最初のパラメーターの戻り値の型を変更したい場合 (この場合はinttoからint option)、ブライアンのソリューションのように、代わりに戻り値の型で継続を使用することもできます。彼の定義のバリエーションは次のとおりです。
let memoC f =
let cache = Dictionary<_,_>()
let rec fn n k =
match cache.TryGetValue(n) with
| true, r -> k r
| _ ->
f fn n (fun r ->
cache.Add(n,r)
k r)
fun n -> fn n id
繰り返しになりますが、CPS 関数を構築するための適切な計算式があれば、次のように再帰関数を定義できます。
fun fib n -> cps {
printfn "%i" n
if n <= 1 then return n
else
let! x = fib (n-1)
let! y = fib (n-2)
return x + y
} |> memoC
これは Brian が行ったこととまったく同じですが、ここの構文の方が理解しやすいと思います。これを機能させるために必要なのは、次の 2 つの定義だけです。
type CpsBuilder() =
member this.Return x k = k x
member this.Bind(m,f) k = m (fun a -> f a k)
let cps = CpsBuilder()