map . foldr function composition - Haskell

Question

So, let's straight to the point.

:t (map.foldr)
(map.foldr) :: (a1 -> a -> a) -> [a] -> [[a1] -> a]

What is [[a1] -> a]? I'm really trying to understand this composition, so I was doing this:

-- map.foldr

    map.foldr :: (a1 -> a -> a) -> [a] -> [[a1] -> a]

    map :: (a1 -> b1) -> [a1] -> [b1]
    (.) :: (y -> w) -> (x -> y) -> x -> w
    foldr :: (a -> b -> b) -> b -> [a] -> b

    y = (a1 -> b1)      w = ([a1] -> [b1])
    x = (a -> b -> b)   y = (b -> [a] -> b)

    y = (a1 -> b1)  
    y = (b -> [a] -> b)
_________________________

What happens in this point? Thank you!

Answer 1

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).

Answer 2

To continue where you left off, the two definitions of y must be equal:

y = (a1 -> b1) = (b ->  [a] -> b)
               = (b -> ([a] -> b))

so we can conclude that:

a1 = b
b1 = [a] -> b

The function composition has been supplied two function arguments, so the resulting type is just:

x -> w

But we know:

x = a -> b -> b
w = [a1] -> [b1] = [b] -> [[a] -> b]

So, the result type is:

(x -> w) = ((a -> b -> b) -> ([b] -> [[a] -> b]))
         =  (a -> b -> b) ->  [b] -> [[a] -> b]

which is congruent to:

(a1 -> a -> a) -> [a] -> [[a1] -> a]