haskell - Haskell 中的迭代和垃圾收集

Question

我有一个关于 GHC 如何实现简单代码的问题。性能和技术问题。

这是 John Hughes 的“为什么函数式编程很重要”文章中的一个简单示例。平方根计算。

为了进行计算，我们需要之前的近似值，我们可以使用迭代函数来创建具有近似值的列表:

[a0, f(a0), f(f(a0), ...] 等等

然后 with inside 会在方便的时候停止:

within eps (a:b:xs) = if abs(a-b) < eps then b else within eps (b:xs)

问题是如何在恒定空间中执行此操作？

GC 是否知道在递归调用中，在 eps (b: xs) 内列表的头 a 不再处于范围内，然后将其收集？

如果是这种情况，那么在每次迭代时，GHC 是否总是创建然后销毁内存中的一个位置(变量)？在变量总是被重用的过程语言中，如何才能表现得那么好？

Answer 1

Does the GC know in the recursive call, within eps (b: xs) that head a of the list is no longer in scope and then it is collected?

正确。

If this is the case, then at each iteration, would the GHC always create and then destroy a location in memory (variable)?

对于这个例子，几乎可以肯定是的。在某些情况下，列表融合可以将基于列表的算法转变为紧密的非分配循环；如果您仅使用内置函数来生成和使用列表，则最有可能发生这种情况。

how can this perform as well as in a procedural language where the variable is always reused?

分配器和 GC 已针对进行大量分配和收集进行了调整。通常分配只是碰撞一个指针。有时你会遇到 GC，但只需要从第一代复制一个 Float 到第二代(或者只需要一个 Float 和一些闭包或其他什么 - 你会得到这个想法，大部分数据不需要被触及，因为它是不可访问的)，这同样非常便宜。显然，存在一些开销，但通常您所做的计算足够复杂，以至于需要花费大部分运行时间。