Trying to write `map` using `foldr`

Question

I had an exam where I was forced to create the function map using foldr I know by now there is a wirde and short way to do it which is map f = foldr ((:) . f) []. My shot was

map' :: (a->b) -> [a] ->[b]
map' f [] = []
map' f [x] = foldr f x [] : []
map' f (x:xs) (foldr f x []) ++ map' f xs

my problem is that f need to be of type a->b->b and it is a->b. How can i force it to work? how can i change f to fit this implemention?

Answer 1

It seems that you want to apply foldr on one element, then recursively adds up the result.

It seems the ability of foldr to accumulate is not used.

To implement map by foldr, you will want the accumulated result by foldr to be like a mapped list.

So that's why in the short way foldr fold (:).f (a->[b]->[b]) instead of f (a->b).

After you apply f onto an element x, then you will want to make it as an accumulated result (:) (f x) [] => (f x):[] => [f x]

foldr ((:).f) [] [x1,x2,x3] = (f x1):(f x2):(f x3):[] = [f x1, f x2, f x3] = map f [x1,x2,x3].

Edit:

Recursion without foldr

map' f [] = []
map' f [x] = [f x]
map' f (x:xs) = map' f [x] ++ map' f xs

So if you really want to use both recursion and foldr:

map' :: (a->b) -> [a] ->[b]
map' f [] = []
map' f [x] = foldr ((:).f) [] [x]
map' f (x:xs) = (foldr ((:).f) [] [x]) ++ map' f xs

f :: a -> b
(:).f :: a -> [b] -> [b]

Then every time foldr will only be applied to one element. It will just be like [f x].

Answer 2

Recursing on the structure of the list with your custom map' is unlikely to give you an answer that your exam grader will be happy with, regardless of how you manipulate f. You will essentially end up using foldr in the most trivial way possible. To see why, note that the below is an implementation of map.

map f [] = []
-- Yes you could use (:) here, but this mirrors your example better
map f (x : xs) = [f x] ++ (map f xs)

You're already done! No foldr necessary. If we preserved this approach, you would only use foldr to create [f x] which is rather boring (something like foldr (\_ _ -> [f x]) [] would suffice, see what I mean by boring?).

So really the key is to realize that foldr takes care of the recursion for you, or equivalently that foldr already does a list traversal for you.

One possible approach for intuition is to think of foldr as accumulating into another collection, rather than folding into a single element.

-- Hmmm well this just accumulates a list into another list, 
-- resulting in an identical list
foldr (\x acc -> x : acc) xs
-- What if we changed x along the way?
foldr (\x acc -> (f x) : acc) xs -- This is it!

If you're curious how to get to (:) . f, @Ben's answer does a great job of walking through it.

Answer 3

foldr is a very general recursive list processing function, because of how it mirrors the structure of the list type it self:

data [a]        -- a list is either
  = a : [a]     -- a head element, plus a tail list
  | []          -- or an empty list

foldr :: (a -> b -> b)    -- given a handler for a head element and the
                          --   result of processing the tail
      -> b                -- and a "handler" for an empty list
      -> [a]              -- foldr turns a list
      -> b                -- into a single result

That might need a bit more unpacking than I could fit in inline comments.

We all know a list has two cases, either a cons cell : containing a single element and the rest of the list, or an empty list containing no information.

Well, the first two parameters to foldr are exactly instructions for how to handle each of these two cases. The a -> b -> b function parameter is the handler for the cons : case. When foldr encounters a cons cell like x : xs it will call the handler with x as the first argument, which fits type a. The second argument it passes to the handler is not the rest of the list xs, but the result of foldr processing xs - remembering that foldr ultimately turns a list into a b, that fits the second parameter of the a -> b -> b type.

The "handler" for the empty list case is much simpler; since an empty list contains no more information, we don't need a function that can transform the information inside an empty list into a b, we can just use a b value as the result immediately.

Because of this mirrored structure, a lot of recursive functions can be implemented by calling foldr with appropriate arguments. The exam question is certainly asking you to make use of this and implement map in terms of foldr without using recursion; the recursion inside foldr is enough.

So your answer must look like this:

map f xs = foldr _ _ xs

You don't need to use multiple cases to handle an empty list or a cons cell; we handle those cases by the two arguments we give to foldr. The empty list case is obvious, since map f [] == [], so lets go ahead and fill in foldr's "empty list handler":

map f xs = foldr _ [] xs

The : case is handled by the first argument. Remember what we said above; that is supposed to be a function taking an element of the list and the result of processing the tail of the list. And remembering that we're configuring this foldr to do the job of map, the "result of processing the tail of the list" is going to be the equivalent of having already mapped f over the tail of the list. So all we need to do is write a function that can take an element of the original list, apply f to it, and glue it onto the front of the already-mapped list. So:

map f xs = foldr applyCons [] xs
  where applyCons elem mappedRest = f elem : mappedRest

-- or

map f xs = foldr (\x xs' -> f x : xs') [] xs

I would expect something like either of those to get full marks on an exam question.

---

Just for a little follow up though, lets see how the "short and weird" version you quoted map f = foldr ((:) . f) [] is actually basically the same as the above, just with a few fairly mechanical simplifications applied. Starting from here:

map f xs = foldr (\x xs' -> f x : xs') [] xs

We can see that both sides of that definition are just <something> xs; that is, xs is the last argument on both sides of the = and isn't otehrwised used anywhere else. So we can drop it from both sides (this process is known as "eta-reduction" in unnecessarily fancy jargon), leaving us with:

map f = foldr (\x xs' -> f x : xs') []

Then we can use : inside the lambda in its prefix form instead of as an operator:

map f = foldr (\x xs' -> (:) (f x) xs') []

Which reveals that in the lambda function xs' is also the last thing in the list of parameters and the last argument on the right hand side, so we can drop that too:

map f = foldr (\x -> (:) (f x)) []

And then you may or may not remember (but should be able to figure out if you remember how it works) that the definition of the composition . operator is:

f . g = \x -> f (g x)

Or in our case:

(:) . f = \x -> (:) (f x)

The right hand side of that is exactly the lambda we were working with, so we can replace it with the left hand side:

map f = foldr ((:) . f) []

Which is our weird and short version.

The reason I said it was "basically the same" as the longer versions you might have found more readable, is that I could rewrite the long version into the short version without thinking at all about map or foldr, or the purpose of any of this code at all. I "merely" applied some knowledge I had about functions in general (and the . operator in particular) to make some changes that always result in equivalent code, without needing any knowledge of what the code is doing. In an exam situation you almost certainly won't be expected to produce the shortest expressions (unless it was an exam for an advanced course, perhaps). And even in real programming "short" isn't a virtue in and of itself (the virtue is "simpler and clearer", which sometimes means shorter), so stopping at the longer non-weird version is fine if that is clearer to you.