null and length
For lists, we have functions null and length. null tells us whether a
list is empty:
>>> null []
True
>>> null [1]
False
length tells us the length of a list:
>>> length [1,5,1]
3
Similarly, we can ask whether a container is empty or how many elements it contains.
The default implementation of null for arbitrary foldable containers is
sneaky:
null :: t a -> Bool
null = foldr (\_ _ -> False) True
Woah. If the container is empty, then the result of foldr is the initial
value, which is True in this case, exactly what we want for empty containers.
If the container is non-empty, then the final result of foldr is obtained by
applying the accumulator function to the first container element and the result
of accumulating the remaining elements recursively. In this case, the
accumulator function does not care what its arguments look like—it uses two
wildcards—and simply returns False. Thus, the result is False for non-empty
containers, again exactly what we want. Incidentally, laziness combined with the
accumulator function not caring about its arguments means that this application
of foldr does not accumulate the whole container. It simply returns True
if the container is empty, and evaluates the accumulator function once to
produce False if the container is non-empty. So, null is a constant-time
operation for most foldable containers.
length is easily implemented using a left-fold:
length :: t a -> Int
length = foldl' (\c _ -> c + 1) 0
For the empty container, the result is simply 0. For a non-empty container, we start with an initial count of 0 and then walk down the container. The accumulator function takes the current count and a container element it does not care about, and returns the current count plus 1. At the end of traversing the container, we thus obtain the total count of all elements in the container.
Maybe we do want to try whether this gives us the results we'd expect not
only for lists but also for Maybe and trees:
>>> null Nothing
True
>>> null (Just 5)
False
The Nothing container is empty, and Just 5 stores an element, so it is
not. Similarly, since Nothing is empty, its length should be 0, whereas
the length of Just 5 should be 1 because it contains a single element:
>>> length Nothing
0
>>> length (Just 5)
1
The empty tree is, well, empty and has no elements:
>>> null Empty
True
>>> length Empty
0
Using the non-empty tree from before, which contains 4 elements, we also obtain the desired results:
>>> tree = Node Empty 5 (Node (Node Empty 3 Empty) 1 (Node Empty 2 Empty))
>>> null tree
False
>>> length tree
4