Haskell 的 foldr/l 和 Clojure 的 reduce

Question

我决定认真对待 Haskell，并且全神贯注于 foldl 和 foldr 的使用。他们真的很像 Clojure 的 reduce - 但我可能错了，很快就遇到了问题，我希望有人能轻松解释。

使用此文档: https://wiki.haskell.org/Foldr_Foldl_Foldl '

在深入实现我自己的 foldr/foldl 版本之前，我决定首先测试 Prelude 中的现有版本:

± |master U:2 ✗| → ghci
GHCi, version 8.6.3: http://www.haskell.org/ghc/  :? for help
Loaded GHCi configuration from /Users/akarpov/.ghc/ghci.conf
Prelude> foldr (+) 0 [1..9999999]
49999995000000
Prelude> foldr (+) 0 [1..99999999]
*** Exception: stack overflow

没有看到(使用 foldl 时结果相同)；我更期待 Clojure 的一些东西:

> (time (reduce +' (range 1 99999999)))
"Elapsed time: 3435.638258 msecs"
4999999850000001

唯一明显(且不相关)的区别是使用 +' 而不是 +，但这只是为了适应 JVM 的类型系统——生成的数字不适合 [默认] Long，并且 +' 将自动使用需要时使用 BigInteger。最重要的是，没有堆栈溢出。因此，这似乎表明 Haskell/Clojure 中的折叠/归约要么实现方式非常不同，要么我对 haskell 实现的使用是错误的。

如果相关，这些是全局项目设置:- 包:[]- 解析器:lts-13.8

Answer 1

问题

作为the Wiki解释说，函数 (+) 的两个参数都是严格的，这意味着当您尝试执行 1 + (2 + 3) 时，您首先需要计算 (2 + 3)。虽然乍一看这似乎不是一个大问题，但当你有一个长列表时它就会成为问题。引用维基，

to evaluate: 1 + (2 + (3 + (4 + (...)))), 1 is pushed on the stack.

Then: 2 + (3 + (4 + (...))) is evaluated. So 2 is pushed on the stack.

Then: 3 + (4 + (...)) is evaluated. So 3 is pushed on the stack.

Then: 4 + (...) is evaluated. So 4 is pushed on the stack.

Then: your limited stack will eventually run full when you evaluate a large enough chain of (+)s. This then triggers the stack overflow exception.

我不太了解 Clojure，但如果 (+') 有效，那么它绝对不需要在缩减之前对两个参数进行评估，这也是 Haskell 中的解决方案.

解决方案

Foldl 不会解决这个问题，因为众所周知 foldl 在返回结果之前必须遍历整个列表两次——这效率不高——即使这样 (+) 也是仍然严格，所以可归约表达式不会被归约。

要解决这个问题，您必须使用非严格函数。在标准 Prelude 中，seq::a -> b -> b 可以完全用于此目的，这就是 foldl' 的工作方式。

再次引用wiki，

foldr is not only the right fold, it is also most commonly the right fold to use, in particular when transforming lists (or other foldables) into lists with related elements in the same order. Notably, foldr will be effective for transforming even infinite lists into other infinite lists. For such purposes, it should be your first and most natural choice. For example, note that foldr (:) []==id.

foldl' 的问题在于它颠倒了列表。如果你有一个不是问题的交换函数，那么如果你的列表是有限的(记住 foldl 必须遍历它)，foldl' 通常更好。另一方面，如果您的功能出于某些原因不一定需要整个列表，或者列表可能是无限的，请选择 foldr