在像 Haskell 这样的函数式语言中，记忆值的生命周期是多长？

Question

在具有惰性语义的纯函数语言（例如 Haskell）中，计算结果会被记忆，以便对具有相同输入的函数进行进一步求值时不会重新计算该值，而是直接从记忆值的缓存中获取该值。

我想知道这些记忆值是否会在某个时间点被回收？

1. 如果是这样，则意味着必须在稍后重新计算记忆值，并且记忆的好处并不那么令人印象深刻。
2. 如果没有，那么好吧，缓存所有内容是很聪明的...但这是否意味着程序 - 如果运行足够长的时间 - 将 总是消耗越来越多的内存？

想象一个程序执行密集的数值分析：例如使用二分法算法查找数十万个数学函数列表的根。

每次程序使用特定实数计算数学函数时，结果都会被记住。但只有很小的概率 在算法过程中，完全相同的实数将再次出现，导致内存泄漏（或者至少，非常糟糕的使用）。

我的想法是，也许记忆值只是“范围”到程序中的某些内容（例如当前的延续、调用堆栈等），但我无法找到关于该主题的实用内容。

我承认我没有深入研究 Haskell 编译器实现（懒惰？），但是请有人向我解释它在实践中是如何工作的？

---

编辑：好吧，我从前几个答案中理解了我的错误：纯粹的语义意味着引用透明性，而这反过来并不意味着自动记忆化，而只是保证不会有任何问题。

我认为网络上的一些文章对此有误导性，因为从初学者的角度来看，引用透明度属性似乎很酷，因为它允许隐式记忆。

Answer 1

Haskell不会自动记忆函数调用，正是因为这会很快消耗大量内存。如果您自己进行记忆，您可以选择记忆函数的范围。例如，假设您的斐波那契函数定义如下：

fib n = fibs !! n
    where fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

这里，记忆化仅在对 fib 的一次调用中完成，而如果您将 fibs 保留在顶层

fib n = fibs !! n

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

，那么记忆列表将一直保留，直到垃圾收集器确定没有更多方法可以从程序的任何部分访问 fib。

Answer 2

我的想法是，也许记忆值只是“范围”到程序中的某些内容（例如当前的延续、调用堆栈等），但我无法找到关于该主题的实用内容。

这是正确的。具体来说，当您看到类似：

fun x y = let
    a = .....
    b = ....
    c = ....
in ....

或等效的 where 子句时，值 a、b 和 c 可能在实际使用之前不会被计算（或者它们可能会立即计算，因为严格性分析器可以证明这些值无论如何都会在稍后计算） ）。但是，当这些值取决于当前函数参数（此处为 x 和 y）时，运行时很可能不会记住 x 和 y 的每个组合以及生成的 a、b 和 c。

另请注意，在纯语言中，根本不记住这些值也是可以的 - 这仅在内存比 CPU 时间便宜的情况下才实用。

所以你的问题的答案是：Haskell 中不存在中间结果的生命周期这样的东西。只能说，需要的时候评估值就会出现。