Lists and Sequences

Usually the first data structure that every programmer learns about are Lists. They are easy to conceive and allow for a great deal of problem definition and solving. Purely functional lists in OCaml are typically defined as:

type 'a list =
 | Nil
 | Cons of 'a * 'a list

This type has two constructors, a Nil indicating an empty List and Cons of 'a * 'a list as an element of type 'a and a pointer to the rest of the list. And if one wishes to get the length of this type of lists, it can do so as:

let rec length_aux acc xs =
 match xs with
 | Nil -> acc
 | Cons (_, xs) -> length_aux (acc + 1) xs

let length list = length_aux 0 list

There is nothing inherintly bad or wrong with what we have done so far. However these lists are assumed to exist in memory and thus are finite. We might find that producing elements on demand, and not as a whole, more interesting as it can allow for potential infinite sequences of elements. In that regard we can revisit our list and add a function of type () -> 'a node that when called produces a new element. These are so called sequences or cascades.

type 'a node =
  | Nil
  | Cons of 'a * 'a t
and
  'a t = unit -> 'a node

And now defining an equivalent length function over sequences:

let rec length_aux acc xs =
  match xs() with
  | Nil -> acc
  | Cons (_, xs) -> length_aux (acc + 1) xs

let length xs = length_aux 0 xs

Strikingly familiar, right? 🙂