How to define map using foldr?

4
votes

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.

2
haskellmapvariable-assignmentfold
Everything is doable without lambdas. Just create a named function that does the same thing. As for how to approach this, figure out how to write id :: [a] -> [a] with foldr. Then remember that id :: [a] -> [a] is the same thing as map (id :: a -> a), and figure out where you need to apply the extra function. - Carl
There is no difference between what you call a "lambda" and any other function. They're all just functions. What's being shown there is the syntax for defining a function without a name. - Chuck
Relevant: web.jaguarpaw.co.uk/~tom/blog/posts/… - Tom Ellis
try wikipedia, en.wikipedia.org/wiki/Fold_(higher-order_function) :) - JJJ
@TomEllis left_fold f z xs = let rs = z : zipWith f xs rs in last rs ; zipWith is a map: zipWith f a b = map (uncurry f) $ zip a b (although, last is kind of a fold...(?)). But, ignoring that, rev xs = left_fold (flip (:)) [] xs (reverse is a left fold); and then right_fold f z xs = let rs = z : zipWith f (rev xs) rs in last rs. cf. stackoverflow.com/a/11951590/849891. - Will Ness

2 Answers

7
votes

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.

5
votes

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.