find

The final generalization I will discuss is

find :: Foldable t => (a -> Bool) -> t a -> Maybe a

It generalizes elem. Where elem asks whether there exists an element in the container that is equal to an element we are searching for, find asks whether there exists an element in the container that satisfies a given predicate. For example,

GHCi

>>> find even [1,2,3]
Just 2
>>> find even [1,3,5]
Nothing

find does not only answer True or False depending on whether an element that matches the predicate is in the container, it also returns the first element matching the predicate that it finds, wrapped in Just. If none of the elements in the container match the predicate, then the result is Nothing.

Here's how we implement find:

find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find pred = getFirst . foldMap (\x -> First (if pred x then Just x else Nothing))

newtype First a = First { getFirst :: Maybe a }

instance Semigroup (First a) where
    First Nothing <> First y = First y
    First x       <> _       = First x

instance Monoid (First a) where
    mempty = First Nothing

The strategy of find is to map every element x in the container to Nothing if it does not satisfy the predicate, and to Just x if it does. Then find reports the first Just value it finds, or Nothing if all values are Nothing.

To implement this idea of finding the first element that is not Nothing, we once again need a newtype wrapper around Maybe, called First.¹ We cannot make Maybe itself a monoid here because there already exists a Monoid instance for Maybe that behaves differently.

The First wrapper implements the idea that "multiplication" of two Maybe values picks the left value if it is not Nothing, even if the right value also isn't Nothing. If the left value is Nothing, then multiplication picks the right value. It is not hard to see that folding a sequence of Maybe values in this fashion produces Nothing if all the elements in the sequence are Nothing, and it produces the leftmost non-Nothing value in the sequence if there is such a value. It also isn't hard to see that First a satisfies the monoid laws.

Again, here is an application to trees:

GHCi

>>> tree = Node Empty 5 (Node (Node Empty 3 Empty) 1 (Node Empty 2 Empty))
>>> find even tree
Just 2
>>> find (\x -> x `mod` 4 == 0) tree
Nothing

If you're like me, you may wonder why we can't just left-fold the container, as in
```
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find pred = foldl pickLeft Nothing
  where
    pickLeft Nothing y | pred y    = Just y
                       | otherwise = Nothing
    pickLeft x       _             = x
```
This achieves the same effect without all the wand waving using yet another custom monoid. The reason why we don't choose this implementation is that it's less efficient. The tail-recursive implementation of foldl, which usually leads to more efficient code, hurts us here. In the real implementation of find using foldMap, the search stops as soon as we find the first element matching the predicate, thanks to laziness. With foldl, the tail recursion means that the final result will be known only after traversing the entire container.

We could of course have obtained an equally efficient implementation as the one using foldMap by using foldr, and this would still avoid the monoid magic using First:
```
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find pred = foldr pickLeft Nothing
  where
    pickLeft x y | pred x    = Just x
                 | otherwise = y
```
This is even more concise than the implementation using foldl. The reason why this implementation effectively stops searching the container as soon as it finds an element x that matches pred is that the branch with pattern guard pred x simply returns Just x without inspecting y. Given lazy evaluation, this means that y is not evaluated at all. But y is produced by folding the "tail" of the container, so this folding simply doesn't happen.

Now, why don't we use this implementation of find via foldr. The answer is that, once we have the First monoid, the implementation via foldMap and First is yet more concise than the one using foldr. The First monoid takes some typing to implement, but it is useful in its own right, to be used in functions other than find. Thus, this effort amortizes itself. ↩