# Association Lists

# 3.8. Association Lists#

A *map* is a data structure that maps *keys* to *values*. Maps are also known as
*dictionaries*. One easy implementation of a map is an *association list*, which
is a list of pairs. Here, for example, is an association list that maps some
shape names to the number of sides they have:

```
let d = [("rectangle", 4); ("nonagon", 9); ("icosagon", 20)]
```

```
val d : (string * int) list =
[("rectangle", 4); ("nonagon", 9); ("icosagon", 20)]
```

Note that an association list isn’t so much a built-in data type in OCaml as a combination of two other types: lists and pairs.

Here are two functions that implement insertion and lookup in an association list:

```
(** [insert k v lst] is an association list that binds key [k] to value [v]
and otherwise is the same as [lst] *)
let insert k v lst = (k, v) :: lst
(** [lookup k lst] is [Some v] if association list [lst] binds key [k] to
value [v]; and is [None] if [lst] does not bind [k]. *)
let rec lookup k = function
| [] -> None
| (k', v) :: t -> if k = k' then Some v else lookup k t
```

```
val insert : 'a -> 'b -> ('a * 'b) list -> ('a * 'b) list = <fun>
```

```
val lookup : 'a -> ('a * 'b) list -> 'b option = <fun>
```

The `insert`

function simply adds a new map from a key to a value at the front
of the list. It doesn’t bother to check whether the key is already in the list.
The `lookup`

function looks through the list from left to right. So if there did
happen to be multiple maps for a given key in the list, only the most recently
inserted one would be returned.

Insertion in an association list is therefore constant time, and lookup is
linear time. Although there are certainly more efficient implementations of
dictionaries—and we’ll study some later in this course—association
lists are a very easy and useful implementation for small dictionaries that
aren’t performance critical. The OCaml standard library has functions for
association lists in the `List`

module; look for `List.assoc`

and the
functions below it in the documentation. What we just wrote as `lookup`

is
actually already defined as `List.assoc_opt`

. There is no pre-defined `insert`

function in the library because it’s so trivial just to cons a pair on.