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`

?

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

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

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

Hope youâ€™ll find that helpful

1 Like