How to define map using foldr?

Question

I've recently began studying Haskell and in one of my assignments I've got an exercise which asks to define the map function in terms of foldr, and I can't for the life of me figure out how to do this. I've searched stack overflow for solutions and came across this one:

How would you define map and filter using foldr in Haskell?

However here the solution involves using lambdas, which I haven't covered yet and I assume that because of this the exercise should be doable without lambdas (although you never know).

I guess what confuses me the most is that map takes in a unary function (e.g. +1), whereas foldr takes a binary function (e.g. +), and I don't really see how to make these two work together.

Answer 1

foldr is actually easy: Given a list (written with : and []) like

a : (b : (c : (d : [])))

then applying foldr h x to it will replace every : with `h` and [] with x:

a `h` (b `h` (c `h` (d `h` x)))

Compare that with what map f would to the list:

f a : (f b : (f c : (f d : [])))

This should guide you in choosing h and x so that foldr h x = map f.

Answer 2

foldr decomposes a list from the right and allows you to thread an accumulated value through the compuation. Since map preserves the length of the list, you need to thread a new list through, which contains the transformed values.

The type of foldr is (a -> b -> b) -> b -> [a] -> b

Your accumulator function takes the state (the new list being constructed) and the current list element, and you need to create a new list which contains the element transformed by the mapping function.

The second argument to foldr is the initial accumulator value, and this is the value returned if the input list is empty, so you should be able to use this to figure out what it should be for you map function.