在像Haskell这样的函数式语言中,memoized值的生命周期是多少？

Question

在具有惰性语义的纯函数语言(例如Haskell)中,计算结果被记忆,因此对具有相同输入的函数的进一步评估不会重新计算该值,而是直接从memoized值的缓存中获取它.

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

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

每次程序评估具有特定实数的数学函数时,结果都将被记忆.但是在算法期间,只有很小的概率才会出现完全相同的实数,导致内存泄漏(或者至少是非常糟糕的使用).

我的想法是,也许memoized值只是"范围"到程序中的某些东西(例如到当前的continuation,调用堆栈等),但我无法找到关于这个主题的实际内容.

我承认我没有深入研究Haskell编译器实现(懒惰？),但是,有人可以向我解释它在实践中是如何工作的吗？

编辑:好的,我从最初的几个答案中理解了我的错误:纯语义意味着参考透明度,这反过来并不意味着自动记忆,但只是保证它没有问题.

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

Answer 1

哈斯克尔并不会自动memoize的函数调用,正是因为这会快速消耗吨的记忆.如果你自己做了memoziation,你可以选择记忆功能的范围.例如,假设你有像这样定义的fibonacci函数:

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)

然后保留memoized列表,直到垃圾收集器可以确定没有更多的方法fibs从程序的任何部分到达.

Answer 2

我的想法是,也许memoized值只是"范围"到程序中的某些东西(例如到当前的continuation,调用堆栈等),但我无法找到关于这个主题的实际内容.

这是对的.具体来说,当你看到类似的东西:

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

或等效的where子句,值a,b和c在实际使用之前可能无法计算(或者可以立即计算它们,因为严格性分析器可以证明以后无论如何都要评估这些值).但是当这些值依赖于当前函数参数(此处为x和y)时,运行时很可能不会记住x和y以及结果a,b和c的每个组合.

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

所以你的问题的答案是:在Haskell中没有中间结果的生命周期.所有人都可以说,评估值将在需要时存在.