Haskell - foldl和foldr？ [英] Haskell - foldl and foldr?

问题描述

foldl 和 foldr 之间的区别只是循环的方向吗？我认为他们做了什么不同，而不仅仅是在方向上吗？

解决方案

如果你的函数不是' t关联（也就是说你关心表达式的方式），例如，

foldr（ - ）0 [1..10] = -5 但是 foldl（ - ）0 [1..10] = -55 。

从小规模来看，这是因为 10-（20-（30））不同于（（10）-20）-30 。

鉴于（+）是关联的（无论您添加子表达式的顺序如何），

foldr（+）0 [1..10] = 55 和 foldl（+）0 [1..10] = 55 。 （++）是另一个关联操作，因为 xs ++（ys ++ zs） code>（xs ++ ys）++ zs （尽管第一个更快 - 不要使用 foldl（++）。

一些函数只能以一种方式工作：

foldr（:) :: [a] - > [ a] - > [a] 但是 foldl（：）是无稽之谈。

看看Cale Gibbard的图表（来自）。

Is difference between foldl and foldr just the direction of looping? I thought there was a difference in what they did, not just in the direction?

解决方案

There's a difference if your function isn't associative (i.e. it matters which way you bracket expressions) so for example,
foldr (-) 0 [1..10] = -5 but foldl (-) 0 [1..10] = -55.
On a small scale, this is because 10-(20-(30)) isn't the same as ((10)-20)-30.

Whereas because (+) is associative (doesn't matter what order you add subexpressions),
foldr (+) 0 [1..10] = 55 and foldl (+) 0 [1..10] = 55. (++) is another associative operation because xs ++ (ys ++ zs) gives the same answer as (xs ++ ys) ++ zs (although the first one is faster - don't use foldl (++).

Some functions only work one way:
foldr (:) :: [a] -> [a] -> [a] but foldl (:) is nonsense.

Have a look at Cale Gibbard's diagrams (from the wikipedia article); you can see f getting called with genuinely different pairs of data:

Another difference is that because it matches the structure of the list, foldr is often more efficient for lazy evaluation, so can be used with an infinite list as long as f is non-strict in its second argument (like (:) or (++)). foldl is only rarely the better choice. If you're using foldl it's usually worth using foldl' because it's strict and stops you building up a long list of intermediate results. (More on this topic in the answers to this question.)

这篇关于Haskell - foldl和foldr？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！