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

问题描述

foldl 和 foldr 的区别仅仅是循环的方向吗?我认为他们所做的有所不同，而不仅仅是方向?

解决方案

如果您的函数不是关联的(即，您将表达式括起来的方式很重要)，则存在差异，例如，
foldr (-) 0 [1..10] = -5 但foldl (-) 0 [1..10] = -55.
这是因为前者等于 1-(2-(3-(4-(5-(6-(7-(8-)-(9-(10 - 0)))))))))，而后者是 ((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10.

鉴于 (+) 是关联的(与添加子表达式的顺序无关)，
foldr (+) 0 [1..10] = 55 和 foldl (+) 0 [1..10] = 55.(++) 是另一个关联操作，因为 xs ++ (ys ++ zs) 给出与 (xs ++ ys) ++ zs<相同的答案/code>(虽然第一个更快 - 不要使用 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.
This is because the former is equal to 1-(2-(3-(4-(5-(6-(7-(8-(9-(10 - 0))))))))), whereas the latter is (((((((((0-1)-2)-3)-4)-5)-6)-7)-8)-9)-10.

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屋！