我有一个功能
myLength = foldl (\ x _ -> x + 1) 0
这会因堆栈溢出而输入10 ^ 6个元素左右而失败(myLength [1..1000000]失败)。我相信这是由于当我将foldl替换为foldl'时，它能正常工作的原因。
到现在为止还挺好。
但是现在我有了另一个功能来反转列表:
myReverse = foldl (\ acc x -> x : acc) []
使用惰性版本的foldl(而不是foldl')
当我做
myLength . myReverse $ [1..1000000]。这次工作正常。我不明白为什么foldl适用于后一种情况而不适用于前一种情况？
这里要澄清的是myLength使用foldl'，而myReverse使用foldl
最佳答案
这是我最好的猜测，尽管我还不是Haskell内部工具的专家。
在构建thunk时，Haskell在堆上分配所有中间累加器变量。
在像myLength中执行加法时，需要将堆栈用于中间变量。参见this page。摘抄:
当我们最终评估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被评估。
等等
请注意，z999999，z999998等从尚未评估的表达式更改为单个列表项是Haskell的日常工作:)
由于z1000000，z999999，z999998等都在堆上，因此这些操作不使用任何堆栈空间。 QED。