首先,我正在阅读的Real World Haskell建议永远不要使用foldl
,而要使用foldl'
。所以我相信它。
但我不清楚什么时候使用foldr
,什么时候使用foldl'
。虽然我可以看到它们的不同工作结构摆在我面前,但我太愚蠢了,不知道什么时候“哪个更好”。我猜在我看来,使用哪一个并不重要,因为它们都产生了相同的答案(不是吗?)。事实上,我之前使用这个结构的经验来自于Ruby的inject
和reduce
,它们似乎没有“左”和“右”版本。(附带问题:他们使用的是哪个版本?)
任何可以帮助像我这样的聪明挑战的人的洞察力都将不胜感激!
发布于 2008-12-21 20:41:42
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
这里一个重要的区别是,如果只使用x
的值就可以计算出f x y
的结果,那么foldr
就不需要检查整个列表。例如
foldr (&&) False (repeat False)
返回False
,而
foldl (&&) False (repeat False)
永不终止。(注意:repeat False
创建了一个无限列表,其中每个元素都是False
。)
另一方面,foldl'
是尾递归和严格的。如果您知道无论如何都必须遍历整个列表(例如,对列表中的数字求和),那么foldl'
比foldr
更有空间效率(也可能是时间效率)。
发布于 2010-01-31 06:40:00
发布于 2008-12-21 19:01:02
它们的语义不同,所以不能简单地将foldl
和foldr
互换。一个从左边折叠元素,另一个从右边折叠。这样,运算符将以不同的顺序应用。这对所有非关联操作都很重要,比如减法。
Haskell.org在这个主题上有一个有趣的article。
https://stackoverflow.com/questions/384797
复制相似问题