关于懒惰

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

这是我最好的猜测，虽然我对哈斯克尔内部没有专家（还）。

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

当执行myLength中的添加时，它需要使用中间变量的堆栈。见this page。摘录：

注意z1000000 = z999999 + 1000000于是1000,000压栈：

当我们最终评估z1000000的问题开始。然后评估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被评估。

等

注意z999999，z999998等。从尚未评估的表达式转换为单个列表项是Haskell的日常工作:)

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