关于懒惰的困惑

Question

我有一个功能

myLength = foldl (\ x _ -> x + 1) 0

在堆栈溢出时失败,输入大约10 ^ 6个元素(myLength [1..1000000]失败).我相信这是因为当我用foldl'替换foldl时,thunk积累,它起作用.到现在为止还挺好.

但现在我有另一个功能来反转列表:

myReverse = foldl (\ acc x -> x : acc) []

它使用懒惰版本foldl(而不是 foldl')

当我这样做 myLength . myReverse $ [1..1000000].这次它运作正常.我不明白为什么foldl适用于后一种情况而不适用于前者？

为了澄清这里myLength使用foldl',而myReverse使用foldl

Answer 1

这是我最好的猜测，尽管我还不是 Haskell 内部的专家。

在构建 thunk 时，Haskell 在堆上分配所有中间累加器变量。

当执行加法时myLength，需要使用堆栈作为中间变量。请参阅此页。摘抄：

当我们最终评估 z1000000 时，问题就开始了：

请注意，z1000000 = z999999 + 1000000。因此 1000000 被压入堆栈。然后对 z999999 进行评估。

请注意，z999999 = z999998 + 999999。因此 999999 被压入堆栈。然后计算 z999998：

请注意，z999998 = z999997 + 999998。因此 999998 被压入堆栈。然后对 z999997 进行求值：

然而，在执行列表构建时，我认为会发生以下情况（这是猜测开始的地方）：

评估 z1000000 时：

请注意，z1000000 = 1000000 : z999999。因此 1000000 存储在 z1000000 中，以及指向 z999999 的链接（指针）。然后对 z999999 进行评估。

请注意，z999999 = 999999 : z999998。因此 999999 存储在 z999999 中，并附有指向 z999998 的链接。然后对 z999998 进行评估。

ETC。

请注意，z999999、z999998 等从尚未计算的表达式更改为单个列表项是 Haskell 的日常事务:)

由于z1000000、z999999、z999998等都在堆上，因此这些操作不使用任何堆栈空间。量子ED。