Can my implementation of filter be improved?

  • A+

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)) [] 


I would only use bool if it let me get rid of the lambda expression, 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 an if expression in the lambda expression.

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

Note that when specialized to functions, f <*> g = /x -> f x (g x). I leave it as an exercise to use that definition to transform bool id . (:) <*> p to /x -> bool id . (x:) (p x).


:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: