NonEmpty 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 nonempty.
Fortunately, you can just use a nonempty list type such as Cons to avoid both bugs and the hassle of Maybe
. For example, since nonempty 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 nonempty lists, since the tail of a nonempty list isn’t necessarily nonempty. This writeup shows how to define nonempty lists in a recursionfriendly way.
Lists
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
NonEmpty Lists
To define a nonempty list type, which we’ll call Cons
, we can just take the definition of List
from above and remove Nil
:
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 NonEmpty Lists
But there is a way to define a nonempty list recursively—as a head element, maybe followed by a tail nonempty 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)
Yeah!
If you’re using a language with a powerful type system, and you know that a list is going to be nonempty, then you may as well let the compiler know this too by using a nonempty list type.
For example:
 In Elm you can use Cons from my elmcons package.
 In Haskell you can use Data.List.NonEmpty from the semigroups package.
 In PureScript you can use Data.NonEmpty from the purescriptnonempty package.
 In Scala you can use scalaz.NonEmptyList.
Yeah!
There was a small discussion of this writeup on lobste.rs

Notice that
Maybe (Cons a)
is isomorphic toList a
, if we treatNothing
as the empty list. So our two definitions ofCons
are equivalent; one is just more convenient for recursion. You can read more about this equivalence in the “List May Be Cons” section of the elmcons documentation. ↩ 
In elmcons, 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)
Of course,
maximum
is already defined by the package, and even if it weren’t you could use a nonempty fold to more easily define it:maximum : Cons comparable > comparable maximum = foldl1 max