Dictionaries and Association Lists

Dictionary operations

A dictionary (or map) associates keys with values. The core operations are:

Operation	Description
lookup	Find the value associated with a key
update	Insert or replace a key-value pair
delete	Remove a key-value pair
empty	The dictionary containing no entries
Missing	Exception raised when a key is not found

An abstract type would hide the internal representation behind these operations. This course does not cover OCaml’s module system, so operations are declared individually.

Association list

The simplest representation is an association list: a list of (key, value) pairs.

lookup

Linear search through the list:

exception Missing

let rec lookup a = function
  | [] -> raise Missing
  | (x, y) :: pairs ->
      if a = x then y
      else lookup a pairs

O(n) time, where n is the number of entries.

update

Simply cons the new pair onto the front:

let update (l, b, y) = (b, y) :: l

O(1) time, which is optimal.

Limitations

Aspect	Behaviour
Lookup speed	O(n) — slow for large dictionaries
Update speed	O(1) — fast
Space usage	Grows with number of updates, not number of distinct keys
Ordering required?	No — only equality on keys

The space problem is significant: obsolete entries accumulate and are never removed. Deleting an entry would require finding it first, which would increase update from O(1) to O(n). Association lists are acceptable only when there are few keys in use, or when fast updates matter more than fast lookups.