Store Sequences of Data with Lists

When modeling real-world phenomena, we often need to model an ordered sequence of data of the same type, such as a sequence of integers 1, 2, 3 or of strings "Joe", "Bob", "Lena". If a 2D point is represented as a pair of x and y coordinates, we might want to model a sequence of 2D points (1.0, 1.0), (2.0, 1.0), (3.0, 0.0). Most functional programming languages, including OCaml, provide the list data structure for representing these kinds of data.

Construct and destruct lists

There are two data constructors to construct a list. The first constructor, [](read as nil), creates an empty list. An empty list contains no elements.

The second data constructor, :: (read as cons) takes two arguments—the first element of the list and another list. For instance, we can use :: to create a list containing the integer 2 by consing 2 to the empty list [].

2::[]

The list containing 1 and 2 in that order is constructed by consing 1 onto the list, 2::[].

1::(2::[])

For constructing lists, OCaml provides syntactic sugar that looks more familiar.

[1; 2; 3]

When we write [1; 2; 3], OCaml internally desugars — or translates — the expression into (1::(2::(3::[]))).

The way we use :: to construct a list by consing an element to the beginning of an existing list reveals that the list in OCaml is a singly linked list. The following diagram shows how the [1; 2; 3] list is represented as a singly linked list whereby the empty list, [], signals the end of the list: