Non-Empty Recursion in Elm
Elm requires functions to be total, one consequence of which is that functions on lists must handle the empty list. For example, since the empty list has no head element,
List.head has the type:
List.head : List a -> Maybe a
Haskell, on the other hand, allows partial functions, so you can write a function on lists which doesn’t handle the empty list. So Haskell’s
head just crashes if you give it an empty list, and has the type:
head :: [a] -> a
I like Elm’s approach since it eliminates an entire class of bugs, but it can be annoying if you know that your list is non-empty.
Fortunately, you can just use a non-empty list type such as Cons to avoid both bugs and the hassle of
Maybe. For example, since non-empty lists always have a head element,
Cons.head has the type:
Cons.head : Cons a -> a
But things can get tricky if you want to recurse on non-empty lists, since the tail of a non-empty list isn’t necessarily non-empty. This writeup shows how to define non-empty lists in a recursion-friendly way.
The classic definition of lists in languages like Elm is that they are either the empty list
Nil or they are a
Cons of a head element and a tail list:
type List a = Nil | Cons a (List a)
So the list
[1, 2, 3] would be
Cons 1 (Cons 2 (Cons 3 Nil)).
And since Elm functions are total and must handle all cases, the head of a list is:
head : List a -> Maybe a head list = case list of Nil -> Nothing Cons first rest -> Just first
To define a non-empty list type, which we’ll call
Cons, we can just take the definition of
List from above and remove
type Cons a = Cons a (List a)
So now we always have a head, and no longer need Maybe:
head : Cons a -> a head (Cons first rest) = first
But if we want to implement something recursive, such as the maximum element of a Cons, we run into trouble:
maximum : Cons a -> a maximum (Cons first rest) = case rest of Nil -> first _ -> max first (maximum ???) -- rest is a List, -- not a Cons, -- so we can't recurse
Since Cons is defined in terms of List, we can’t easily recurse on it.
Recursive Non-Empty Lists
But there is a way to define a non-empty list recursively—as a head element, maybe followed by a tail non-empty list:1
Cons a = Cons a (Maybe (Cons a))
Now we can recurse easily:2
maximum : Cons a -> a maximum (Cons first rest) = case rest of Nothing -> first Just rest -> max first (maximum rest)
If you’re using a language with a powerful type system, and you know that a list is going to be non-empty, then you may as well let the compiler know this too by using a non-empty list type.
- In Elm you can use Cons from my elm-cons package.
- In Haskell you can use Data.List.NonEmpty from the semigroups package.
- In PureScript you can use Data.NonEmpty from the purescript-nonempty package.
- In Scala you can use scalaz.NonEmptyList.
There was a small discussion of this writeup on lobste.rs
Maybe (Cons a)is isomorphic to
List a, if we treat
Nothingas the empty list. So our two definitions of
Consare equivalent; one is just more convenient for recursion. You can read more about this equivalence in the “List May Be Cons” section of the elm-cons documentation. ↩
In elm-cons, since Elm discourages exposing type constructors, you use the uncons’ function to recurse on a Cons:
maximum : Cons comparable -> comparable maximum c = case uncons' c of (first, Nothing) -> first (first, Just rest) -> max first (maximum rest)
maximumis already defined by the package, and even if it weren’t you could use a non-empty fold to more easily define it:
maximum : Cons comparable -> comparable maximum = foldl1 max