foldl . foldr function composition - Haskell

Question

So, I'm really frying my brain trying do understand the foldl.foldr composition. Here is a example:

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]

The result is 22, but what's really happening here?

To me it looks like this is what is happening: foldl (+) 1 [6,15]. My doubt is related to the foldr part. Shouldn't it add the 1 to all the sub-lists? Like this: foldr (+) 1 [1,2,3]. In my head the 1 is added just one time, is it right? (probably not, but I want to know how/why!).

I'm very confused (and perhaps making all the confusion, haha). Thank you!

Answer 1

(foldl.foldr) (+) 1 [[1,2,3],[4,5,6]]

becomes

foldl (foldr (+)) 1 [[1,2,3],[4,5,6]]

So you get

foldl (foldr (+)) (foldr (+) 1 [1,2,3]) [[4,5,6]]

after the first step of foldl, or

foldl (foldr (+)) 7 [[4,5,6]]

if we evaluate the applied foldr (unless the strictness analyser kicks in, it would in reality remain an unevaluated thunk until the foldl has traversed the entire list, but the next expression is more readable with it evaluated), and that becomes

foldl (foldr (+)) (foldr (+) 7 [4,5,6]) []

and finally

foldl (foldr (+)) 22 []
~> 22

Answer 2

Let's examine foldl . foldr. Their types are

foldl :: (a -> b -> a) -> (a -> [b] -> a)
foldr :: (c -> d -> d) -> (d -> [c] -> d)

I intentionally used distinct type variables and I added parentheses so that it becomes more apparent that we view them now as functions of one argument (and their results are functions). Looking at foldl we see that it is a kind of lifting function: Given a function that produces a from a using b, we lift it so that it works on [b] (by repeating the computation). Function foldr is similar, just with arguments reversed.

Now what happens if we apply foldl . foldr? First, let's derive the type: We have to unify the type variables so that the result of foldr matches the argument of foldl. So we have to substitute: a = d, b = [c]:

foldl :: (d -> [c] -> d) -> (d -> [[c]] -> d)
foldr :: (c -> d   -> d) -> (d -> [c] -> d)

So we get

foldl . foldr :: (c -> d -> d) -> (d -> [[c]] -> d)

And what is its meaning? First, foldr lifts the argument of type c -> d -> d to work on lists, and reverses its arguments so that we get d -> [c] -> d. Next, foldl lifts this function again to work on [[c]] - lists of [c].

In your case, the operation being lifted (+) is associative, so we don't have care about the order of its application. The double lifting simply creates a function that applies the operation on all the nested elements.

If we use just foldl, the effect is even nicer: We can lift multiple times, like in

foldl . foldl . foldl . foldl
    :: (a -> b -> a) -> (a -> [[[[b]]]] -> a)

Answer 3

Actually, (foldl.foldr) f z xs === foldr f z (concat $ reverse xs).

Even if f is an associative operation, the correct sequence of applications matters, as it can have an impact on performance.

We begin with

(foldl.foldr) f z xs
foldl (foldr f) z xs

writing with g = foldr f and [x1,x2,...,xn_1,xn] = xs for a moment, this is

(...((z `g` x1) `g` x2) ... `g` xn)
(`g` xn) ((`g` xn_1) ... ((`g` x1) z) ... )
foldr f z $ concat [xn,xn_1, ..., x1]
foldr f z $ concat $ reverse xs

So in your case the correct reduction sequence is

(foldl.foldr) 1 [[1,2,3],[4,5,6]]
4+(5+(6+(  1+(2+(3+  1)))))
22

To wit,

Prelude> (foldl.foldr) (:) [] [[1..3],[4..6],[7..8]]
[7,8,4,5,6,1,2,3]

---

Similarly, (foldl.foldl) f z xs == foldl f z $ concat xs. With snoc a b = a++[b],

Prelude> (foldl.foldl) snoc [] [[1..3],[4..6],[7..8]]
[1,2,3,4,5,6,7,8]

Also, (foldl.foldl.foldl) f z xs == (foldl.foldl) (foldl f) z xs == foldl (foldl f) z $ concat xs == (foldl.foldl) f z $ concat xs == foldl f z $ concat (concat xs), etc.:

Prelude> (foldl.foldl.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[1,2,3,4,5,6,7,8]
Prelude> (foldl.foldr.foldl) snoc [] [[[1..3],[4..6]],[[7..8]]]
[7,8,1,2,3,4,5,6]
Prelude> (foldl.foldl.foldr) (:) [] [[[1..3],[4..6]],[[7..8]]]
[7,8,4,5,6,1,2,3]