In the last post, I talked about catamorphisms in Haskell.  Specifically, the advantages of the foldr1 or foldl1 option in Haskell.  Namely, (1) not needing to specify the base case and (2) preserving polymorphisms in all applicable types.  In this post, I will show another way to fold nonempty list without using foldr1 or foldl1 in Haskell.  This technique has the same two advantages as mentioned, and it works for both OCaml and Haskell!

Proving Nonemptyness

Note that I’m talking about folding nonempty lists here.  To get the advantages of nonempty list folds, we have to pay the price, namely, that the fold doesn’t work on empty lists.  Haskell throws an exception when the input list to foldr1 or foldl1 is empty.

For a list to be nonempty, it has to have at least one element.  Any list that has at least one element must have a head (the first element of the list).  Therefore, if a list has a head, it must be nonempty.  One can check if a list has a head easily in OCaml and Haskell.  The head of an empty list is ill-defined, and both OCaml and Haskell throw an exception in such a case.

E.g., in OCaml, we can use the hd function in the List module to extract the head of a list:

utop # List.hd [1;2;3];;
- : int = 1
(* When the list is empty, head is ill-defined, and OCaml throws an exception. *)
utop # List.hd [];;
Exception: Failure "hd".

Similarly in Haskell, we can use the Data.List library to extract the head of a list:

Prelude> head [1,2,3]
1
--When the list is empty, Haskell throws an exception.
Prelude> head []
*** Exception: Prelude.head: empty list

In other words, a nonempty list always has a head!  We can use the head as the base case for a fold of a nonempty list!

Using the Head as the Base Case

We can define a function that finds the minimum element of a list using foldr1 or foldl1 in Haskell (as in the last post):

Prelude> find_min = foldl1 min

--find_min works for all types such that min is well-defined.
Prelude> find_min [1,2,3]
1
Prelude> find_min ["string","works","too"]
"string"

--Haskell throws an exception when the input list is empty.
Prelude> find_min []
*** Exception: Prelude.foldl1: empty list

In OCaml, by using the head of the input list as the base case, we mimic foldr1 or foldl1 in Haskell (to learn more about function, see this post):

(* Using 'function', we can omit the input list name while pattern matching. *)
utop # let find_min = function hd :: tl -> List.fold_left min hd tl;;

(* As expected, OCaml warns us that the pattern of an empty list is not matched. *)
Characters 15-60:
Warning 8: this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
[]
val find_min : 'a list -> 'a = <fun>

(* find_min works for all applicable types. *)
utop # find_min [1;2;3];;
- : int = 1
utop # find_min ["strings";"works";"too"];;
- : string = "strings"

(* Like foldr1 or foldl1 in Haskell, OCaml throws an exception when the input list is empty. *)
utop # find_min [];;
Exception: Match_failure ("//toplevel//", 1, 15).

We can do the equivalent in Haskell too:

Prelude> find_min (x:xs) = foldl min x xs
Prelude> find_min [1,2,3]
1
Prelude> find_min ["string","works","too"]
"string"
Prelude> find_min []
*** Exception: <interactive>:8:1-32: Non-exhaustive patterns in function find_min

It’s not great to have an exception when the list is empty though.  In the next post, we will see how we can eliminate the exceptions.