是否可以在没有副作用的情况下进行记忆

Question

我有一些 F# 代码可以缓存结果以供将来查找。我的理解是您添加的字典和其他数据结构需要副作用。（即改变字典的状态）这是正确的吗？这是否被认为是不纯的，或者这是否仍在无副作用计算的模型中。

let rec fib =
    let dict = new System.Collections.Generic.Dictionary<_,_>()
    fun n ->
        match dict.TryGetValue(n) with
        | true, v -> v
        | false, _ -> 
            let fibN =
                match n with
                | 0 | 1 -> n
                | _ -> fib (n - 1) + fib(n - 2)
            dict.Add(n, fibN)
            fibN

Answer 1

记忆函数存储结果，因此它不必在使用相同参数的后续调用中计算结果。存储结果的事实是一个副作用，它也是一个记忆函数的定义属性。因此，我得出结论，您问题的答案是 "no."

解决您关于在字典中存储错误值的评论；是的，你是对的，但还有另一个问题不涉及不正确的结果。 Dictionary class 不是线程安全的。如果两个线程同时尝试从 and/or 中读取并写入字典，您可能会遇到异常。例如：

let data = [| 1 .. 20 |]
let fibs = data |> Array.Parallel.map fib

当我在 F# 交互中多次运行时，我没有遇到任何异常，但经过某些更改后，我得到了 System.ArgumentException:

An item with the same key has already been added.

变化是这些；在每种情况下，我在第一次或第二次尝试时都遇到了异常：

检测使用 printfn
将数字类型更改为 uint64（删除 printfn 诊断）
将数字类型更改为 float（即 System.Double）
将数值类型更改为bigint

Answer 2

为了重申评论中提到的内容，您可以将记忆提取到高阶函数中，该函数将 return 作为参数传入的函数的记忆版本：

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

通过这样做，您实际上可以使 memoized 函数变得纯粹，并且 memoization 成为实现细节。您发布的代码将这两个问题纠缠在一起，推理起来并不那么简单。

请注意，记忆递归函数有点棘手 - 您需要以适合记忆的方式构造要记忆的函数。

这里的一个单独问题是您可以运行解决的并发问题。为了解决这些问题，您可以锁定 dict.Add:

...
let v = f x
lock dict <| fun () ->
    if not <| dict.ContainsKey(x) then
       dict.Add(x, v)
v

或者用 ref 单元格代替 Map （在这种情况下，您可能遇到的任何并发问题仍然存在，但本质上不再是灾难性的） .

是否可以在没有副作用的情况下进行记忆

Is memoizing possible without side effects

f#

functional-programming

memoization

side-effects