Is it possible to define foldr using map?

Question

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!

Answer 1

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 :)

Answer 2

The simplest way to look at it is to see that map preserves the spine of the list. If you look at the more general fmap (which is map, but not just for lists but for Functors in general), it's even a law that

fmap id = id

There are many ways to "cheat," but in the most direct interpretation of your question, folds are simply more general than maps. There is a nice trick that's used in Edward Kmett's Lens library quite a lot. Consider the Const monad, which is defined as follows:

newtype Const a b = Const { runConst :: a }

instance Functor (Const a) where fmap _ (Const a) = Const a
instance (Monoid a) => Monad (Const a) where
    return _ = Const mempty
    Const a >>= Const b = Const (a <> b)

Now you can formulate a fold in terms of the monadic map operation mapM, as long as the result type is monoidal:

fold :: Monoid m => [m] -> m
fold = runConst . mapM Const