Using foldr to define map and filter

The patterns of foldr and foldl occur in surprising places. I don't have a good eye to see those yet. It turns out that our good old map and filter are foldr patterns:

-- recursive definition of map and filter
map :: (a -> b) -> [a] -> [b]
map f [] = []
map f (x:xs) = f x : map f xs

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

So, map f applied to empty list is an empty list while the expression for non-empty list involves processing head in a certain way and recursively applying map to tail. This is foldr with \x xs -> f x : xs as our function:

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

Similarly, filter for non-empty list processes the head and recursively apply filter to tail:

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

Prelude> (map' (^2) . filter' odd) [1..10]
[1,9,25,49,81]

Cool!