# How to make this partial-match exhaustive?

A lazy list implementation.

In ocaml5 + utop, it works with warnings:

``````type 'a seq =
| Nil
| Cons of 'a * (unit -> 'a seq);;

let head (Cons (x, _)) = x;;
let tail (Cons (_,xf)) = xf ();;

let rec from k = Cons (k, fun() -> from (k+1));;
let it = from 1;;

head (tail (tail it));; => 3
``````

This code compiles on the older version of OCaml, but with dune+ocaml5, it got rejected because

``````10 | let head (Cons (x, _)) = x;;
^^^^^^^^^^^^^^^^^
Error (warning 8 [partial-match]): this pattern-matching is not exhaustive.
Here is an example of a case that is not matched:
Nil
``````

However, when I try to fix the code by making it exhaustive, an error occurs

the `head` will be `'a seq seq -> 'a seq` rather than `'a seq -> 'a`

``````type 'a seq =
| Nil
| Cons of 'a * (unit -> 'a seq);;

| Cons (x,_) -> x
| Nil -> Nil;;

let tail = function
| Cons (_,xf) -> (xf ());
| Nil -> Nil;;

let rec from k = Cons (k, fun() -> from (k+1));;

let it = from 1;;

``````
``````17 | (head (tail (tail it)));;
^^^^^^^^^^^^^^^^
Error: This expression has type int seq
but an expression was expected of type 'a seq seq
Type int is not compatible with type 'a seq
``````

Whatâ€™s the correct way to define `head`?

You need to decide how youâ€™re going to handle the head of an empty list. You canâ€™t return `Nil` in this case. It doesnâ€™t have the right type. The type of `head` is `'a seq -> 'a`. But `Nil` is of type `'a seq`.

There is in fact no good value to return as the head of an empty list. A common solution is to raise an exception for this case.

2 Likes

There is in fact no good value to return as the head of an empty list.

Yes, indeed. I had been thinking about what to return but failed.

Raise an exception does make the code compile `:)`

``````exception Nope
type 'a seq =
| Nil
| Cons of 'a * (unit -> 'a seq);;
| Cons (x,_) -> x;
| Nil -> raise Nope;;
let tail = function
| Cons (_,xf) -> (xf ());
| Nil -> Nil;;
let rec from k = Cons (k, fun() -> from (k+1));;
let it = from 1;;
let rec get n s=
match n, s with
| 0, _ -> []
| _, Nil -> []
| n, Cons (x, xf) -> x :: get (n-1) (xf ());;
get 10 (from 60);;

``````

An exception that is commonly used for these kinds of situations is `Not_found` to indicate that an expected value was not found. This exception is built-in.

1 Like

What you really want is this type:

``````type 'a seq = Cons of 'a * (unit -> 'a seq)

let head (Cons (x, _)) = x
let tail (Cons (_, xf)) = xf ()
``````

More OCaml has a dedicated section on the matter (chapter 2): More OCaml: Algorithms, Methods & Diversions â€” OCaml from the Very Beginning

Here are some of my notes, having worked a bit on that chapter:

``````(*
`lazylist` represents infinitely-long lists.
It has no tail, but a "tail function".
It has no `Nil` constructor because the list has no end.
*)
type 'a lazylist = Cons of 'a * (unit -> 'a lazylist)

(* Build a lazylist up to `n` integer *)
let rec lseq n = Cons (n, fun () -> lseq (n + 1))

(*
Implement lazy head, lazy tail and other lazy functions...

When we apply the unit, we force the evaluation of the tail.
*)
let lhd (Cons (n, _)) = n
let ltl (Cons (_, tf)) = tf ()
let%test _ = 8 = (lseq 8 |> lhd)
let%test _ = 9 = (lseq 8 |> ltl |> lhd)
``````