foldr与foldl(或foldl')的含义
J C*_*per 150 recursion haskell functional-programming fold
首先,我正在阅读的真实世界Haskell表示永远不会使用foldl而是使用foldl'.所以我相信它.
但我对什么时候使用foldrvs. 朦胧foldl'.虽然我可以看到他们如何以不同的方式摆放在我面前的结构,但是当"哪个更好"时,我太愚蠢了.我想在我看来似乎并不重要,因为它们都产生相同的答案(不是吗？).事实上,我以前使用这个结构的经验来自Ruby inject和Clojure reduce,它们似乎没有"左"和"右"版本.(附带问题:他们使用哪个版本？)
任何有助于像我这样的智能挑战的洞察力都会非常感激!
Chr*_*way 167
对于递归foldr f x ys地方ys = [y1,y2,...,yk]看起来像
f y1 (f y2 (... (f yk x) ...))
而foldl f x ys看起来像的递归
f (... (f (f x y1) y2) ...) yk
这里的一个重要区别是,如果f x y只能使用值来计算结果x,那么foldr就不需要检查整个列表.例如
foldr (&&) False (repeat False)
返回False而
foldl (&&) False (repeat False)
永远不会终止.(注意:repeat False创建一个无限列表,其中每个元素都是False.)
另一方面,foldl'尾递归和严格.如果您知道无论如何都必须遍历整个列表(例如,对列表中的数字求和),那么foldl'比空间更多(并且可能是时间)效率更高foldr.
- 为避免混淆,请注意括号不显示实际的评估顺序.由于Haskell是惰性的,因此将首先评估最外层表达式. (23认同)
- 在foldr中,它计算为f y1 thunk,因此它返回False,但是在foldl中,f不能知道它的任何参数.在Haskell中,无论是否是尾递归,它都会导致thunk溢出,即thunk是太大.foldl'可以在执行时立即减少thunk. (2认同)
Kon*_*lph 33
他们的语义不同,所以你不能只交换foldl和foldr.一个元素从左侧向上折叠,另一个元素从右侧折叠.这样,操作员以不同的顺序应用.这对于所有非关联操作都很重要,例如减法.
Haskell.org有一篇关于这个主题的有趣文章.
- @ Evi1M4chine 没有任何区别是微不足道的。相反，它们是实质性的（并且，是的，在实践中很有意义）。事实上，如果我今天写这个答案，它会更加强调这种差异。 (4认同)
Axm*_*an6 18
最理想的原因foldl'是foldl99%的用途是它可以在大多数用途的恒定空间中运行.
采取这个功能sum = foldl['] (+) 0.当foldl'使用时,会立即计算总和,因此应用于sum无限列表将永远运行,并且很可能在恒定空间中运行(如果您使用的是Ints,Doubles,Floats等Integers将使用多于常量空间,如果数字变得大于maxBound :: Int).
有了foldl,就会建立一个thunk(就像一个如何获得答案的方法,可以在以后评估,而不是存储答案).这些thunk可以占用很多空间,在这种情况下,评估表达式比存储thunk要好得多(导致堆栈溢出......并导致你......哦,没关系)
希望有所帮助.
new*_*cct 14
顺便说一句,Ruby inject和Clojure reduce是foldl(或者foldl1,取决于你使用的版本).通常,当一种语言中只有一种形式时,它是一个左侧折叠,包括Python reduce,Perl List::Util::reduce,C++ accumulate,C#Aggregate,Smalltalk inject:into:,PHP array_reduce,Mathematica Fold等.Common Lisp reduce默认左折,但有一个右折叠选项.
- 这个评论很有帮助,但我会很感激. (2认同)
正如康拉德指出的那样,他们的语义是不同的.它们甚至没有相同的类型:
ghci> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
ghci> :t foldl
foldl :: (a -> b -> a) -> a -> [b] -> a
ghci>
例如,列表追加运算符(++)可以用foldras 实现
(++) = flip (foldr (:))
而
(++) = flip (foldl (:))
会给你一个类型错误.
| 归档时间： |
|
| 查看次数： |
30460 次 |
| 最近记录： |