Can my implementation of filter be improved?

Question

An exercise in Haskell from First Principles says to implement filter using foldr and this is what I came up with but it feels and looks clunky. Is there a more natural way to implement it with a foldr?

import Data.Bool
myFilter :: (a -> Bool) -> [a] -> [a]
myFilter f = foldr (\x -> bool (++ []) ((:) x) (f x)) []

Answer 1

I would only use bool if it let me get rid of the lambda expression simply, by composing a call to bool with the predicate p: bool iffalse iftrue . p. However, p isn't the only function that needs to be called on a list element; (:) does as well. You could use the Applicative instance for functions, to write

myfilter p = foldr (bool id . (:) <*> p) []  -- yuck

but in this case I would just use a plain if expression, inside the lambda expression:

myfilter p = foldr (\x -> if p x then (x:) else id) []  -- much clearer!

---

Note that when specialized to functions, the Applicative's (<*>) operator is defined as f <*> g = \x -> f x (g x). I leave it as an exercise to use that definition to transform bool id . (:) <*> p into \x -> bool id (x:) (p x).

Answer 2

You can use the Applicative instance of (->) a to make the lambda cleaner. But, if you want to use foldr, I don't think there's any substantial change you can effect:

myFilter f = foldr (bool id <$> (:) <*> f) []

bool id <$> (:) <*> f means \x -> bool id ((:) x) (f x). bool id has type ([a] -> [a]) -> Bool -> ([a] -> [a]). (:) has type a -> [a] -> [a], and f has type a -> Bool. When (<$>) and (<*>) are used in this way, you can think of it as pretending that (:) and f don't have an a argument, making them [a] -> [a] and Bool, respectively, applying them to bool id to get a [a] -> [a], and then ending the lie by reintroducing the a argument, making a a -> [a] -> [a]. The operators are in charge of threading that a around, so you don't need a lambda abstraction.

Answer 3

Rather than merely searching for a more elegant implementation, it would might help you more to learn an elegant process of searching for an implementation. This should make it simpler to find elegant solutions.

For any function h on lists we have that,

h = foldr f e 

if and only if

h [] = e
h (x:xs) = f x (h xs)

In this case your h is filter p for some boolean function p that selects which elements to keep. Implementing filter p as a "simple" recursive function is not too hard.

filter p [] = []
filter p (x:xs) = if p x then x : (filter p xs) else (filter p xs)

The 1st line implies e = []. The 2nd line needs to be written in the form f x (filter p xs) to match the equation of h above, in order for us to deduce which f to plug in the foldr. To do that we just abstract over those two expressions.

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

So we have found that,

e = [] 
f x ys = if p x then x: ys else ys

It therefore follows,

filter p = foldr (\y ys -> if p y then y : ys else ys) []

To learn more about this method of working with foldr I recommend reading "A tutorial on the universality and expressiveness of fold" by Graham Hutton.

Some added notes:

In case this seems overly complicated, note that while the principles above can be used in this "semi rigorous" fashion via algebraic manipulation, they can and should also be used to guide your intuition and aid you in informal development.

The equation for h (x:xs) = f x (h xs) sheds some clarity on how to find f. In the case where h is the filtering function you want an f which combines the element x with a tail that has already been filtered. If you really understand this it should be easy to arrive at,

f x ys = if p x then x : ys else ys