Haskell- write map function using foldr

1
votes

I am trying to write the map function using foldr. The problem is that when I ran this code :

> myMap f xs = foldr (\ acc x -> acc :(f x)) [] xs

I have the following problem:

No instance for (Num [a0]) arising from a use of 'it'

but when I run

myMap f xs = foldr (\x acc-> (f x):acc) [] xs

It works perfectly. Any ideas why?

2
haskell
As a useful exercise, you can try to expand map (+10) [1,2] with both definitions and observe that the first one is not working, and possibly understand what's wrong with it. – chi

2 Answers

5
votes

The error you posted is not coming from your definition of myMap, it's coming from how you're using it. The type of the first myMap is ([a] -> [a]) -> [a] -> [a], which does not match the type of Prelude.map. In the second one you've swapped your variable names and also which one you're applying f to. The compiler doesn't care what you name the arguments in your lambda being passed to foldr, so foldr (\x acc -> f x : acc) is identical to foldr (\foo bar -> f foo : bar). That may be what's tripping you up here.

The second one works because (to put it simply) it's correct. In the first you're applying f to your accumulator list x (even though you have a variable named acc it's not your accumulator), so f must take a list and return a list. In the second you're applying f to each element, then prepending that to your accumulator list. If you had myMap (+1), it would have the type

myMap (+1) :: Num [a] => [a] -> [a]

Which says that you must pass it a list of values [a] where [a] implements Num, and currently there is no instance for Num [a], nor will there ever be.

TL;DR: In the first one you're applying your mapped function to your accumulator list, in the second one you're applying the mapped function to each element.

5
votes

the type of foldr is

foldr :: (a -> b -> b) -> b -> [a] -> b

therefore the binary operation that foldr uses to traverse and accumulate the list has type (a -> b -> b),it first take an element of the list (type a)then the accumulator (type b) resulting in an expression of type b.

So, your first myMap function does not work becuase you are using "acc" and "x" in reverse order. You want to apply f to x then append it to the acummulator of type b ( a list in this case)