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!
(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
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With