elem

Next is the elem function

elem :: Eq a => a -> t a -> Bool

which we already discussed for lists. It checks whether a given element is part of the container:

GHCi

>>> 3 `elem` [1,2,3]
True
>>> 4 `elem` [1,2,3]
False

Given an element of type a and a collection of as, it decides whether the element is in the collection. To perform this test, we need a to support equality testing. Thus, we need the Eq a type constraint.

The default implementation of elem uses any, which is a function that is not part of the Foldable class but is supported by all foldable containers. We'll discuss it at the end of this chapter, along with a few other useful functions for foldable containers.

For now, it suffices to know that any pred xs is True if and only if there exists an element in xs for which the predicate pred is true. This gives the following type signature for any:

any :: Foldable t => (a -> Bool) -> t a -> Bool

Using this function, elem can be implemented as

elem = any . (==)

Again, this may be a bit terse, but it is useful to get used to defining functions via function composition. Let's once again use equational reasoning to figure out that this is the correct implementation. What we want is that

y `elem` xs = any (\x -> y == x) xs

We want to test every element x in xs whether it is equal to y, and we want to return True if there exists at least one element that is equal to y. Here's how we obtain the definition elem = any . (==) from this more verbose definition:

y `elem` xs = any (\x -> y == x) xs    -- Definition of `elem`
elem y xs   = any (\x -> y == x) xs    -- Convert to using elem in prefix notatation
elem y      = any (\x -> y == x)       -- Drop the common argument xs
elem y      = any (\x -> (==) y x)     -- Convert to using (==) in prefix notation
elem y      = any ((==) y)             -- (\x -> (==) y x) applies ((==) y) to x,
                                       -- so (\x -> (==) y x) is the same as ((==) y)
elem y      = (any . (==)) y           -- Definition of function composition
elem        = any . (==)               -- Drop the common argument y

Once again, elem doesn't work only for lists (using the same tree we have used previously):

GHCi

>>> 1 `elem` Nothing
False
>>> 1 `elem` Just 1
True
>>> 1 `elem` Just 2
False
>>> 5 `elem` tree
True
>>> 5 `elem` Empty
False
>>> 4 `elem` tree
False