How to make this partial-match exhaustive?

Learning
1

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);;

let head = function 
  | 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;;

(head (tail (tail it)));; 

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?

2

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
3

Thanks for speedy reply.

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);;
let head  = function 
  | 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;;
(head (tail (tail it)));;
let rec get n s=
  match n, s with
  | 0, _ -> []
  | _, Nil -> []
  | n, Cons (x, xf) -> x :: get (n-1) (xf ());;
get 10 (from 60);;
4

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
5

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)

Hope you’ll find that helpful :slight_smile:

1 Like