F# 中的通用记忆功能

Question

我对 Fsharp 中的通用记忆功能有疑问：

let memoize f =
    let dict = new Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | (true, v) -> 
            v
        | _ ->
            let temp = f(n)
            dict.Add(n, temp)
            temp

如果我用斐波那契数列为例：

let rec fib = memoize(fun n ->
    if n = 1 then 1
    elif n = 2 then 1
    else fib (n - 1) + fib (n - 2) )

那么每次迭代都会创建一个新的字典，带有映射的字典不是总是会被清除吗？但是，该函数确实显示它创建了一个包含所有节点的字典，您能否详细说明一下，先谢谢了！

编辑：

我尝试将斐波那契函数修改为

let rec fib i = memoize(fun n ->
    if n = 1 then 1
    elif n = 2 then 1
    else fib (n - 1) + fib (n - 2) ) i

因为我想摆脱警告（对于之前的斐波那契函数）：

将对正在定义的对象的此递归引用和其他递归引用将检查初始化的健全性 在运行时通过使用延迟引用。这是因为您正在定义一个或多个递归对象，而不是递归函数。

然后每次字典都会启动（它没有被记忆），我无法理解它

Answer 1

您可能需要 一个记忆 y 组合器。

如果您分解递归，不直接递归并调用作为参数传递的函数，则可以轻松访问中间结果以进行记忆。

let fib f = function
| 1 | 2 -> 1
| n -> f (n - 1) + f (n - 2)

此函数可以使用标准 y-combinator 运行。由于不涉及记忆，因此需要很长时间才能完成。

let rec Y f x = f (Y f) x

Y fib 45
// val it : int = 1134903170

记忆的版本几乎立即返回。

let memoize f =
    let d = new System.Collections.Generic.Dictionary<_,_>()
    let rec g x =
        match d.TryGetValue x with
        | true, res -> res
        | _ -> let res = f g x in d.Add(x, res); res
    g

memoize fib 45
// val it : int = 1134903170