Explanation of map functions (using foldr) in Haskell?

Question

I'm trying to define the map function using foldr

I have found the two following solutions, however I'm not quite sure how they are working.

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

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

I'm quite new to Haskell and foldr, so I'm struggling to understand what ((:) . f) in the first solution and what (\x xs -> f x : xs) in the second solution do.

I also don't get how foldr is able handle the empty list case.

It would be much appreciated if I could get a simple step by step explanation of this, in layman's terms.

The expression \x xs -> f x : xs is a lambda expression, and (:) . f is the pointfree version of it. — Mark Seemann
\x xs -> f x : xs == \x xs -> (:) (f x) xs == \x -> (:) (f x) == (:) . f. — chepner
do you understand what does (:) do? or .? or what is lambda expression? or what is lambda function? these are all really prerequisites to this question. try asking one question at a time. then there's the foldr tag. try exploring it. there's also a page on Wikipedia. try looking at stackoverflow.com/tags/haskell/info for resources for learning Haskell. — Will Ness

Andrew Ray Andrew Ray · Accepted Answer · 2020-04-29T12:49:03

Both (\x xs -> f x : xs) and (:) . f mean the same thing. They're both functions that take two arguments, apply f to the first argument, and then cons that onto the second argument.

So what does foldr do when given an empty list? It simply returns the starting value, which in these examples is [].

Here is the implementation of foldr from Hackage:

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Explanation of map functions (using foldr) in Haskell?

1 Answers