Is it possible to define foldr using map?
fold, haskell, higher-order-functions, map-function
Solution
Let's start with some type signatures.
foldr :: (a -> b -> b) -> b -> [a] -> b
map :: (a -> b) -> [a] -> [b]
We can simulate `map` using `fold` because `fold` is a universal operator (here's a more mathematical yet quite friendly paper on this property).
I'm sure that there's some creative way of using `map` to simulate `foldr`. That can certainly be a fun exercise. But I don't think there's a straight-forward, not "crazy pointfree" solution, and in order to explain it let's forget about `foldr` for a moment and concentrate on a much simpler accumulation function:
sum :: [Int] -> Int
`sum == foldr (+) 0`, which means `foldr` implements `sum`. If we can implement `foldr` with `map` we can definitely implement `sum` with `map`. Can we do it?
I think `sum`'s signature is a crashing blow - `sum` returns an `Int`, and `map` always returns a list of something. So maybe `map` can do the heavy-lifting, but we'll still need another function of type `[a] -> a` in order to get the final result. In our case, we'll need a function of type `[Int] -> Int`. Which is quite unfortunate, because that's exactly what we were trying to avoid in the first place.
So I guess the answer is: you can implement `foldr` using `map` - but it'll probably require using `foldr` :)
Problem
After I defined `map` using `foldr` a question came to my mind: If it is possible to define `map` using `foldr`, what about the opposite? From my point of view it is not possible, but I can't find a proper explanation. Thanks for the help!