Understanding Haskell's filter

Question

I understand that Haskell's filter is a high order function (meaning a function that takes another function as a parameter) that goes through a list checking which element fulfills certain boolean condition.

I don't quite understand its definition:

filter:: (a->Bool)->[a]->[a]
filter p [] = []
filter p (x:y) | p x = x:filter p y
               | otherwise = filter p y

I understand that if I pass an empty list to the function, it would just return an empty list, but how do I read the last two lines?

Answer 1

It uses guards which if you are coming from a language with a C style syntax are a bit similar to the switch structure.

The last pattern reads: If the function p evaluates to true with the argument x then return the head of the list and the filtered tail of the list. Otherwise just return the filtered tail of the list.

You could also rewrite it like so:

filter p (x:y) = if (  p x ) then
                     x:filter p y
                 else
                     filter p y

Answer 2

Consider the description of filter in the docs:

filter, applied to a predicate and a list, returns the list of those elements that satisfy the predicate; i.e.,

filter p xs = [x | x <- xs, p x]

To explain it to someone who doesn't understand list comprehensions, you might say filter has three cases:

1. (the easy case) when the list to be filtered is empty, the result is also empty
2. when the head of the list to be filtered satisfies the predicate, it's part of the result
3. otherwise, skip the head and filter the rest of the list

These cases correspond one-to-one with the last three lines of the definition in your question.

Small touches can make the definition more idiomatic and therefore easier to read:

filter _ []      = []
filter p (x:xs)
  | p x          = x : filter p xs
  | otherwise    =     filter p xs

For an empty list, the predicate can be anything at all, and the underscore shows explicitly that it's unimportant in that case.

Rather than matching against (x:y), using (x:xs)—think: "ex and exes"—emphasizes that you're separating a list into its head (of type a) and tail (of type [a], i.e., list of a).

Finally, lining up the recursive calls to filter easily allows the reader to see that the latter case omits x.