13

在 Haskell 中 有很多关于、和的好问题和答案。foldlfoldrfoldl'

所以现在我知道：
1）foldl很懒
2）不要使用foldl，因为它会炸毁堆栈
3）使用foldl'，因为它很严格（ish）

如何foldl评估：
1）创建了一大堆 thunk
2）在 Haskell 完成创建 thunk 后，thunk 减少了
3）如果有太多 thunk 则溢出堆栈

我感到困惑的是：
1）为什么在所有重击之后必须发生减少？
2）为什么不foldl评估就像foldl'？这只是实现的副作用吗？
3) 从定义来看，foldl它看起来可以使用尾递归来有效地评估——我如何判断一个函数是否真的会被有效地评估？如果我不想让我的程序崩溃，我似乎不得不开始担心 Haskell 中的评估顺序。

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

更新：看来我的问题的答案与范式、弱范式和头部范式以及 Haskell 对它们的实现有关。
但是，我仍在寻找一个示例，其中更急切地评估组合函数会导致不同的结果（崩溃或不必要的评估）。

4

4 回答 4

8

简短的回答是，在 中foldl f，情况不一定f是严格的，因此可能过于急于减少预先的 thunk。但是，实际上通常是这样，因此您几乎总是希望使用foldl'.

我对另一个问题的评估顺序和工作方式进行了更深入的解释foldlfoldl'。它相当长，但我认为它应该为你澄清一些事情。

于 2011-09-20T15:24:19.963 回答
4

你知道，根据定义：

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' 的区别只是上面的表达式在每次递归中都被强制计算，所以最后你有一个弱头正常形式的值。

于 2011-09-20T15:28:12.733 回答
1

我仍在寻找一个示例，其中更急切地评估组合功能会导致不同的结果

一般的经验法则是永远不会使用foldl. 总是使用foldl'，除非你应该使用foldr。我想你知道的足够foldl了解为什么应该避免它。

参见：Real World Haskell > 函数式编程# Left folds, laziness, and space leaks

但是，您的问题忽略了foldr. 有趣的foldr是它可以产生增量结果，同时foldl'需要遍历整个列表才能产生答案。这意味着foldr的惰性允许它处理无限列表。还有一些关于这类事情的详细问题和答案。

提出这个问题后，让我试着简洁地回答你的问题。

1）为什么在所有重击之后必须进行还原？

减少只发生在严格点。例如，执行 IO 是一个严格点。foldl'用于seq添加没有的附加严格点foldl。

2) 为什么不像 foldl' 那样评估 foldl？这只是实现的副作用吗？

因为额外的严格点foldl'

3) 从定义来看， foldl 在我看来就像一个尾递归函数——我如何判断一个函数是否会被有效地评估？如果我不想让我的程序崩溃，我似乎不得不开始担心 Haskell 中的评估顺序。

您需要了解更多关于惰性求值的知识。惰性求值并不是 Haskell 独有的，但 Haskell 是极少数默认惰性求值的语言之一。对于初学者，请记住始终使用foldl'，您应该没问题。

如果有一天懒惰真的让你陷入困境，那么你可能应该确保你了解懒惰和 Haskell 的严格点。您可能会说，上述理论日是默认懒惰学习的严格点。

另见：PLAI > 第三部分：懒惰

于 2011-09-20T18:17:29.713 回答
0

如果我不想让我的程序崩溃，我似乎不得不开始担心 Haskell 中的评估顺序。

在我看来，如果你想让你的程序不崩溃，最好的选择是（根据投入的产出从好到坏排名）： 1. 给它足够的资源。2. 改进你的算法。3. 进行微优化（其中之一是foldl'）。

所以，与其担心评估的顺序，我宁愿首先担心要评估的内容（foldr足够了吗？我可以不折叠它吗？）。在此之前，我会增加可用的堆栈空间。

您不会将整个程序限制为 8MB 的 RAM，对吗？那你为什么要限制堆栈空间呢？只需将堆栈空间增加到 4GB，然后在某些东西真正占用大量堆栈空间时开始担心（就像您对堆内存所做的那样）。

并在某种程度上回答foldl懒惰的问题：

foldl (\x y -> y) undefined [undefined, 8] -- evaluates to 8
foldl' (\x y -> y) undefined [undefined, 8] -- fails to evaluate
于 2011-09-20T17:22:40.017 回答