Why does foldr invert foldl's parameters?

Question

This is a very, very simple foldl function: it takes a list, and returns the same list:

identityL :: (Integral a) => [a] -> [a]
identityL xs = foldl (\ acc x -> acc ++ [x]) [] xs

I tried to do the same thing with foldr, thinking that all I had to do was change foldl to foldr and flip "acc" and "[x]" around the "++". But apparently, you need to flip the parameters as well:

identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ x acc -> [x] ++ acc) [] xs

This seems very counter-intuitive, for a function that seems to serve the purpose of linearly processing a list against an accumulator. I am probably approaching the concept incorrectly; is there a simple model of the fold that justifies the weirdness of flipping the parameters?

EDIT: This was silly; as pointed out, the parameter orderings offset each other. The following code works:

identityR :: (Integral a) => [a] -> [a]
identityR xs = foldr (\ acc x -> [acc] ++ x) [] xs

I saw this before, but it bothers me because the acc should be a list and not need list encapsulation, whereas the x should.

However, when you look at what the folds are really doing, it makes perfect sense to invert the x and acc variables.

Given the list [1,2,3], identityL is successively ++'ing an [x] to the existing acc:

((([] ++ [1]) ++ [2]) ++ [3])

whereas identityR is successively ++'ing an acc to the starting [x]:

([1] ++ ([2] ++ ([3] ++ [])))

Answer 1

Both foldr and foldl pass the list to the function with the arguments in the same order.

foldr (+) 0 [1, 2, 3] = 1 + (2 + (3 + 0))
foldl (+) 0 [1, 2, 3] = ((0 + 1) + 2) + 3

That's all there is to it.

> foldr (\x y -> "(" ++ show x ++ " + " ++ y ++ ")") "0" [1, 2, 3]
"(1 + (2 + (3 + 0)))"
> foldl (\x y -> "(" ++ x ++ " + " ++ show y ++ ")") "0" [1, 2, 3]
"(((0 + 1) + 2) + 3)"

Math

Suppose you have a monoid, M:

identity :: M
op :: M -> M -> M

-- Monoid laws:
-- x `op` (y `op` z) = (x `op` y) `op` z
-- x `op` identity = x
-- identity `op` x = x

The way foldr and foldl are defined, foldr and foldl always give the same result, assuming op is total. They're just different ways of parenthesizing the same expression.

foldr op identity == foldl op identity

For example,

concat :: [[a]] -> [a]
-- both definitions give same result
concat = foldr (++) []
concat = foldl (++) []

sum :: Num a => [a] -> a
-- both definitions give same result
sum = foldr (+) 0
sum = foldl (+) 0

product :: Num a => [a] -> a
-- both definitions give same result
product = foldr (*) 1
product = foldl (*) 1

For non-associative operations, this is irrelevant because foldr and foldl won't generally give the same result. For commutative operations, this is irrelevant because foldr and foldl will give the same result no matter what order the arguments go in. This is only helpful for monoids in general.

Or, put another way, you can think of foldr and foldl as tools for transforming the free monoid (a.k.a the list) into another monoid of your choosing.

Answer 2

If you think of foldr as replacing (:) and [] in the list, then the order of arguments passed to the function makes perfect sense:

xs =           x1  :  x2  :  x3  :  ...  :  []
foldr f a xs = x1 `f` x2 `f` x3 `f` ... `f` a