foldl懒惰怎么样？

Question

有很多很好的问题和答案对foldl,foldr以及foldl'在Haskell.

所以现在我知道:
1)foldl是懒惰的
2)不要使用,foldl因为它可以炸毁堆栈
3)使用foldl'而不是因为它是严格的(ish)

如何foldl评估:
1)创建了一大堆thunks
2)在Haskell完成创建thunk之后,thunk被减少
3)如果有太多的thunk,则溢出堆栈

我对此感到困惑:
1)为什么减少必须在所有thunk之后发生？
2)为什么foldl评估不像foldl'？这只是一个实施副作用吗？
3)从定义看,foldl看起来可以使用尾递归有效地评估 - 我如何判断一个函数是否真的会被有效地评估？如果我不希望我的程序崩溃,似乎我必须开始担心Haskell中的评估顺序.

提前致谢.我不知道我对评估的理解foldl是否正确 - 如有必要,请提出更正建议.

---

更新:看起来我的问题的答案与Normal Form,Weak Normal Form和Head Normal Form以及Haskell的实现有关.
但是,我仍然在寻找一个例子,更加热切地评估组合函数会导致不同的结果(崩溃或不必要的评估).

Answer 1

简短的回答是,foldl f不一定f是严格的情况,因此可能过于急于减少前面的风险.但是,在实践中它通常是,所以你几乎总是想要使用foldl'.

我写了一个更深入的解释,说明评估顺序foldl和foldl'另一个问题的工作原理.它相当长,但我认为它应该为你澄清一些事情.

Answer 2

你知道，根据定义：

foldl op start (x1:x2:...:xN:[]) = ((start `op` x1) `op` x2) ...

Foldl 中执行此操作的行是：

foldl op a (x:xs) = foldl op (a `op` x) xs

你是对的，这是尾递归，但观察表达式

(a `op` x)

是惰性的，在列表的末尾，将构建一个巨大的表达式，然后将其减少。与 Foldl' 的区别只是上面的表达式在每次递归中都被强制求值，所以最后你会得到一个弱头范式的值。