# 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!