Store Sequences of Data with Lists
Learn to use the list data structure to store sequences of data.
We'll cover the following
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:
Get hands-on with 1200+ tech skills courses.