From what I understand about folds in Haskell, foldl (-) 0 [1..5] gives a result of -15 by calculating 0-1-2-3-4-5, and foldr (-) 0 [1..5] gives a result of -5 by calculating 5-4-3-2-1-0. Why is it then that both foldl (++) "" ["a", "b", "c"] and foldr (++) "" ["a", "b", "c"] give a result of "abc", and the result of foldr is not, instead, "cba"?
Is there something I'm missing in understanding the differences between foldl and foldr?
I think this part from the docs makes it clearer:
In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left:
foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...). . .
In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:
foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
If you look at the example breakdown, the concatenation foldr is equivalent to:
"a" ++ ("b" ++ ("c" ++ ""))
And for foldl, it would be equivalent to:
(("" ++ "a") ++ "b") ++ "c"
For string concatenation, these are the same.
For subtraction however,
1 - (2 - (3 - 0))
Gives a different result than:
((0 - 1) - 2) - 3
Actually foldr (-) 0 [1..5] equals 3, because it's:
(1 - (2 - (3 - (4 - (5 - 0))))
The answer to this question is in the type of foldr function:
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
As we see, (a -> b -> b) function has iterated element as the first argument and accumulator as the second one. That's why with foldr (++) "" ["a", "b", "c"] we have:
("a" ++ ("b" ++ ("c" ++ "")))
any (>5) xs can be expressed as foldr False (\v a -> if v>5 then True else a) xs.Seen symbolically as a "translation" of the fold, 0-1-2-3-4-5 by itself is ill-defined. The order of operations must be specified.
In fact, whatever the operator, the order is
foldl (-) 0 [1..5] = ((((0 - 1) - 2) - 3) - 4) - 5 -- = -15
foldr (-) 0 [1..5] = 1 - (2 - (3 - (4 - (5 - 0)))) -- = 3
For the (++) though, both orderings result in the same result, when "" is used in place of 0.
0-1-2-3-4-5 is defined; it's sum [0, -1, -2, -3, -4, -5], which means the binary - is left associative (:i (-) says infixl 6 -). Thus it matches the foldl case here.
- seen symbolically, as the stand-in for any possible operator, it is not fully defined without specifying the associativity (as the fixity declaration in Haskell does).I found this to be the most instructive way to get the difference (because the idea of 'left associative' is new to me): -- comments reflect :doc foldr and :doc foldl
*Main> foldr (-) 2 [1,4,8] -- foldr f z [a,b,c] == a f (b f(c f z))
3
*Main> 1 - (4 - ( 8 - 2) ) -- foldr right associative
3
*Main> ((2 - 1) - 4) -8 -- foldl left associative
-11
*Main> foldl (-) 2 [1,4,8] -- foldl f z [a,b,c] == ((z f a) f b) f c
-11
foldr (%) d [a,b,c] = a % (b % (c % d)), whereasfoldl (%) d [a,b,c] = ((a % b) % c) % d.