To answer this question it's good to recall what foldr
and map
do.
The more complicated of the two is foldr
, which has type
-- list to be folded
-- v
foldr :: (a -> b -> b) -> b -> [a] -> b
-- ^ ^
--folding function terminal value
The list to be folded is really a chain of conses (:)
and a terminal empty list:
1 : 2 : 3 : []
The action of foldr
is to replace the :
and []
constructors with the folding function and the terminal value, respectively:
foldr (+) 0 (1 : 2 : 3 : []) == 1 + 2 + 3 + 0
The map
function is simpler. One way of thinking of it is as taking a function and a list, and applying the function to every argument of the list:
map :: (a -> b) -> [a] -> [b]
-- ^ ^
-- function list
However, you can also think of it as taking a function, and lifting it to be a function that acts on lists instead:
map :: (a -> b) -> ( [a] -> [b] )
-- ^ ^
-- function function on lists
What does it mean to compose these two functions, map . foldr
? Note that this is just applying the functions one after the other - in particular,
(map . foldr) f == map (foldr f)
Since you apply foldr
first, you must be applying it to a function f :: a -> b -> b
, and you get back another function:
foldr f :: b -> [a] -> b
-- ^ ^
--terminal val list to be folded
Now you apply map
, which lifts the function to act on lists:
map (foldr f) :: [b] -> [[a] -> b]
-- ^ ^
--list of terminal vals functions that fold lists
This type looks odd, but it's valid. Now instead of a single terminal value, you give it a list of terminal values, and you get a list of folding functions back - one for each terminal value that you supplied.
To make it clearer we could look at a particular function, (+)
, which has type
(+) :: Num a => a -> a -> a
If we substitute that into the equation above, we get
(map . foldr) (+) :: Num a => [a] -> [[a] -> a]
-- ^ ^
-- list of terminal vals functions that fold lists
If we now apply it to the list [0, 1, 2]
we get a list of three functions:
(map . foldr) (+) [0,1,2] :: Num a => [[a] -> a]
We can use the map ($x)
idiom to apply each of the functions in the list to a particular argument. It has to be a list of numbers, and I'll choose [3,4,5]
. Watch carefully:
> map ($[3,4,5]) ((map.foldr) (+) [0,1,2])
[12, 13, 14]
The list [3,4,5]
was folded three times using (+)
as the folding function, and each time with a different terminal value:
3 + 4 + 5 + 0 == 12
3 + 4 + 5 + 1 == 13
3 + 4 + 5 + 2 == 14
When the terminal value is 0
, we simply get the sum of the values: 3 + 4 + 5 == 12
. When the terminal value is 1
we get one more than the sum of the values (13
) and when the terminal value is 2
we get two more than the sum of the values (14
).