filter and find

Sometimes, we may want to extract all those elements from a list that meet some condition. filter is the tool for the job. For example,

GHCi

>>> filter even [1,2,3,4,5]
[2,4]

Here's how filter is implemented:

filter :: (a -> Bool) -> [a] -> [a]
filter pred = go
  where
    go (x:xs) | pred x    = x : go xs
              | otherwise =     go xs
    go _                  = []

If we want to find just a single element in the list that meets the given condition, we can use find:

GHCi

>>> import Data.List
>>> find even [1,2,3,4,5]
Just 2
>>> find even [1,3,5]
Nothing

Find can be implemented directly,

find :: (a -> Bool) -> [a] -> Maybe a
find pred = go
  where
    go (x:xs) | pred x    = Just x
              | otherwise = go xs
    go _                  = Nothing

However, we can also implement it with the help of the following little function:

listToMaybe :: [a] -> Maybe a
listToMaybe []    = Nothing
listToMaybe (x:_) = Just x

This is actually nothing but our safe head function discussed earlier. It returns Just the head of the list if the list is non-empty, and Nothing otherwise. To use this function, you need to import the Data.Maybe module.

With the help of listToMaybe, find becomes really easy to implement:

find pred = listToMaybe . filter pred

The logic is that filter produces the list of all elements that meet the given criterion. If this list is empty, listToMaybe turns this into Nothing. If the list is non-empty, listToMaybe turns this into Just the head of the list, so we obtain exactly the correct behaviour of find.

You may wonder whether this implementation of find via filter and listToMaybe is less efficient than the direct implementation of find given above. In most languages, this would be the case because the direct implementation of find stops as soon as it finds the first element that meets the given condition, whereas filter inspects all list elements to decide whether they meet the given condition, and then we use listToMaybe to extract the first element from the list of elements that do. Given Haskell's lazy evaluation, filter pred does not inspect any elements in its input list unless we inspect elements in the result of filter pred. When we do, filter pred inspects exactly as many elements in the input list as necessary to produce the number of elements in the output list we inspect. Since find pred is interested only in the first element that matches the predicate pred, filter pred inspects exactly as many elements in the input list as necessary to find the first element that matches pred or to verify that none of the elements in the input list satisfies pred. That's exactly the same behaviour as exhibited by the direct implementation of find, that is, lazy evaluation makes the implementation of find via filter exactly as efficient as the direct implementation of find.

Exercise

Instead of finding the first or all list elements that satisfy a certain condition, we sometimes want to split a list into two sublists based on some condition. We have already seen partition, which produces two lists containing the elements that do and do not satisfy the condition, respectively:

GHCi

>>> import Data.List
>>> partition even [1,2,3,4,5]
([2,4],[1,3,5])

There are two other functions that have the same type as partition but behave differently:

span  :: (a -> Bool) -> [a] -> ([a], [a])
break :: (a -> Bool) -> [a] -> ([a], [a])

span pred xs splits xs into two lists ys and zs, where ys is the longest prefix of xs whose elements satisfy pred, and zs is the remainder of xs. In other words, span pred xs takes elements from xs and adds them to ys as long as these elements satisfy pred. As soon as it sees an element that does not satisfy pred, it stops and defines zs to be the list of remaining elements in xs:

GHCi

>>> span even [2,8,4,1,10,12,3,7]
([2,8,4],[1,10,12,3,7])

break pred xs does the opposite. It adds elements to ys as long as they don't satisfy pred. As soon as it finds an element that does satisfy pred, it stops and defines zs to be the list of remaining elements in xs:

GHCi

>>> break odd [2,8,4,1,10,12,3,7]
([2,8,4],[1,10,12,3,7])

There also exist two functions takeWhile and dropWhile that return only one of the two lists returned by span. In other words, we have

span pred xs = (takeWhile pred xs, dropWhile pred xs)

only the actual implementation of span is more efficient.

GHCi

>>> takeWhile even [2,8,4,1,10,12,3,7]
[2,8,4]
>>> dropWhile even [2,8,4,1,10,12,3,7]
[1,10,12,3,7]

Implement span and provide implementations of break, takeWhile, and dropWhile that use span as a helper.

Solution

span :: (a -> Bool) -> [a] -> ([a], [a])
span pred = go
  where
    go []           = ([],     [])
    go xs@(x:xs')
        | pred xs   = (x : ls, rs)
        | otherwise = ([],     xs)
      where
        (ls, rs) = go xs'

break :: (a -> Bool) -> [a] -> ([a], [a])
break pred = span (not . pred)

takeWhile, dropWhile :: (a -> Bool) -> [a] -> [a]
takeWhile pred = fst . span pred
dropWhile pred = snd . span pred