How would you define map and filter using foldr in Haskell?
Solution 1
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
Solution 2
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
Solution 3
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.
Solution 4
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
Solution 5
I am new to Haskell (in fact I've found this page asking the same question) but this is my understanding of lists and foldr so far:
- lists are elements that are linked to the next element with the cons
(:)
operator. they terminate with the empty list[]
. (think of it as a binary operator just like addition(+)
1+2+3+4 = 10
,1:2:3:4:[] = [1,2,3,4]
- foldr function takes a function that takes two parameters. this will replace the cons operator, which will define how each item is linked to the next.
- it also takes the terminal value for the operation, which can be tought as the initial value that will be assigned to the empty list. for cons it is empty list
[]
. if you link an empty list to any list the result is the list itself. so for asum
function it is0
. for a multiply function it is1
, etc. - and it takes the list itself
So my solution is as follows:
filter' p = foldr (\x n -> if p x then x : n else n) []
the lambda expression is our link function, which will be used instead of the cons (:)
operator. Empty list is our default value for an empty list. If predicate is satisfied we link to the next item using (:)
as normal, else we simply don't link at all.
map' f = foldr (\x n -> f x : n) []
here we link f x
to the next item instead of just x
, which would simply duplicate the list.
Also, note that you don't need to use pattern matching, since we already tell foldr what to do in case of an empty list.
I know this question is really old but I just wanted to answer it anyway. I hope it is not against the rules.
Related videos on Youtube
klactose
Just a guy trying to figure it all out while enjoying the journey!
Updated on May 08, 2022Comments
-
klactose almost 2 years
I'm doing a bit of self study on functional languages (currently using Haskell). I came across a Haskell based assignment which requires defining map and filter in terms of foldr. For the life of me I'm not fully understanding how to go about this.
For example when I define a map function like:
map' :: (a -> b) -> [a] -> [b] map' f [] = [] map' f (x:xs) = foldr (\x xs -> (f x):xs) [] xs
I don't know why the first element of the list is always ignored. Meaning that:
map' (*2) [1,2,3,4]
results in [4,6,8] instead of [2,4,6,8]
Similarly, my filter' function:
filter' :: (a -> Bool) -> [a] -> [a] filter' p [] = [] filter' p (x:xs) = foldr (\x xs -> if p x then x:xs else xs ) [] xs
when run as:
filter' even [2,3,4,5,6]
results in [4,6] instead of [2,4,6]
Why would this be the case? And how SHOULD I have defined these functions to get the expected results? I'm assuming something is wrong with my lambda expressions...
-
dave4420 about 13 yearsThe cases for
[]
are redundant ---foldr
does the right thing when you pass it[]
. -
x13n about 13 yearsYup. But Alessandro already wrote it. So for further improvements, check out his answer.
-
Dan Burton about 13 yearsPrecicely. Thus it should become clear that
map' f xs
instead ofmap' f (x:xs)
should solve the problem. -
Ed'ka about 13 yearsBtw GHC can be an aid in seeing it when option
-Wall
is used:Warning: Defined but not used: 'x'
(or, for the original code:This binding for 'x' shadows the existing binding
) -
fuz about 13 yearsNow, you should have enough karma and a nice badge on top ;)
-
klactose about 13 yearsThanks, you were right... my usage of x & xs was confusing me! This really made it much clearer.
-
klactose about 13 yearsThanks for letting me know that it is a bit redundant to add a case for the empty list.
-
AndrewC over 11 yearsThis answers a question in the title, very neatly, but it would be even more helpful if you explained, and yet more helpful if you answered the other questions in the question.
-
paluh over 10 yearsFollowing @coffeMug suggestion, parameters can be reduced inside lambda too:
filter p = foldr (\x -> if p x then (x:) else id) []
-
Justin L. over 8 yearsis there anyone who really finds
(:).f
easier to read than\x xs -> f x : xs
? -
dfeuer over 8 years@paluh, while this is all rather silly, you can import
Data.Bool
and usefilter p = foldr (bool id . (:) <*> p) []
. Going to extremes,filter = (`foldr` []) . (bool id . (:) <*>)
. -
Vombat almost 8 years@Justin L a mathematician. ;-)
-
Justin L. almost 8 years@coffeMug I'll dare you to find a mathematician who does :P
-
palik over 4 yearsplease, replace
map' f (x:xs)
bymap' f xs
as suggested by Dan Burton -
Will Ness about 3 yearsno, there's no suggestion in Dan Burton's comment to make such an edit to this answer.