# Maps as Association Lists

The simplest implementation of a map in OCaml is as an association list. We've seen that implementation a number of times so far. So here it is, offered without further explanation:

module ListMap : Map = struct

(** AF: [[(k1, v1); (k2, v2); ...; (kn, vn)]] is the map
{k1 : v1, k2 : v2, ..., kn : vn}.
If a key appears more than once in the list, then in the map it is
bound to the left-most occurrence in the list. For example,
[[(k, v1); (k, v2)]] represents {k : v1}. The empty list represents
the empty map.
RI: none. *)
type ('k,'v) t = ('k * 'v) list

(** Efficiency: O(1). *)
let insert k v m =
(k, v) :: m

(** Efficiency: O(n). *)
let find = List.assoc_opt

(** Efficiency: O(n). *)
let remove k lst =
List.filter (fun (k', _) -> k <> k') lst

let empty = []

(** Efficiency: O(1). *)
let of_list lst =
lst

(** [keys m] is a list of the keys in [m], without
any duplicates.
Efficiency: O(n log n). *)
let keys m =
m |> List.map fst |> List.sort_uniq Stdlib.compare

(** [binding m k] is [(k, v)], where [v] is the value that [k]
binds in [m].
Requires: [k] is a key in [m].
Efficiency: O(n). *)
let binding m k =
(k, List.assoc k m)

(** Efficiency: O(n log n) + O(n) * O(n), which is O(n^2). *)
let bindings m =
List.map (binding m) (keys m)

end