How to define map using foldr?
dictionary, fold, haskell, variable-assignment
Solution
`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`.
Problem
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.