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 (** [find 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>
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.
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
actually already defined as
List.assoc_opt. There is no pre-defined
function in the library because it’s so trivial just to cons a pair on.