Use foldr to define map in Haskell,

Question

I'm new to Haskell and try to understand the map function.

I understand the following so far.

map::(a->b)->[a]->[b]
map f (x:xs) = f x : map f xs

But I don't understand following definition: Use foldr to define map

map'::(a->b)->[a]->[b]
map' f = foldr ( (:).f ) []

Can anyone explain the above map' definition and why it is same as map

Daniel Wagner Daniel Wagner · Accepted Answer · 2016-05-19T01:40:53

Let's look at the source of foldr:

foldr k z = go where
    go []     = z
    go (x:xs) = k x (go xs)

Now let's compare the definition of map to the definition of go above:

map f []     = []
map f (x:xs) = f x : map f xs

It looks very similar, doesn't it? Let's rewrite the second clause to pull out the part that combines x with the recursive call's result:

map f []     = []
map f (x:xs) = (\v vs -> f v : vs) x (map f xs)

Now the parallel is very clear; we can even write some names to crystallize the parallel:

map f []     = z              where z = []
map f (x:xs) = k x (map f xs) where k = \v vs -> f v : vs

Just substitute go everywhere you see map f in the above and you'll see that the definitions are identical! So in the spirit of DRY, we can try to reuse foldr for the above:

map f = foldr (\v vs -> f v : vs) []

That gets you the big idea on how to get from map to foldr. Getting all the way to the definition you gave is then just some syntax tricks. We'll concentrate on the function argument to foldr now:

\v vs -> f v : vs
= { writing the infix operator prefix instead }
\v vs -> (:) (f v) vs
= { eta reduction }
\v -> (:) (f v)
= { definition of function composition }
\v -> ((:) . f) v
= { eta reduction }
(:) . f

So using this chain of reasoning, we can reach the final form

map f = foldr ((:) . f) []

Use foldr to define map in Haskell,

3 Answers