How would you define map and filter using foldr in Haskell?

I wish I could just comment, but alas, I don't have enough karma.

The other answers are all good ones, but I think the biggest confusion seems to be stemming from your use of x and xs.

If you rewrote it as

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

you would clearly see that x is not even mentioned on the right-hand side, so there's no way that it could be in the solution.

Cheers

In your definitions, you are doing pattern matching for x:xs, which means, when your argument is [1,2,3,4], x is bound to 1 and xs is bound to the rest of the list: [2,3,4].

What you should not do is simply throw away x: part. Then your foldr will be working on whole list.

So your definitions should look as follows:

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

and

filter'             :: (a -> Bool) -> [a] -> [a]
filter' p []        = []
filter' p xs        = foldr (\x xs -> if p x then x:xs else xs ) [] xs

I would define map using foldr and function composition as follows:

map :: (a -> b) -> [a] -> [b]
map f = foldr ((:).f) []

And for the case of filter:

filter :: (a -> Bool) -> [a] -> [a]
filter p = foldr (\x xs -> if p x then x:xs else xs) []

Note that it is not necessary to pass the list itself when defining functions over lists using foldr or foldl. The problem with your solution is that you drop the head of the list and then apply the map over the list and this is why the head of the list is missing when the result is shown.

For your first question, foldr already has a case for the empty list, so you need not and should not provide a case for it in your own map.

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

The same holds for filter'

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

Nothing is wrong with your lambda expressions, but there is something wrong with your definitions of filter' and map'. In the cons case (x:xs) you eat the head (x) away and then pass the tail to foldr. The foldr function can never see the first element you already ate. :)

Alse note that:

filter' p = foldr (\x xs -> if p x then x : xs else xs) []

is equivalent (η-equivalent) to:

filter' p xs = foldr (\x xs -> if p x then x : xs else xs) [] xs