:PROPERTIES: :ID: 2111ce7d-0f49-48e2-93bf-50cba426f970 :mtime: 20231020020344 :ctime: 20231020020342 :END: #+title: association list #+filetags: :project:public: * Definition An association list is a concept in programming where you use a list of pairs to represent a map In a pseudo-haskell syntax, we might write #+BEGIN_SRC haskell Map a b = List (a,b) #+END_SRC * Examples of Association Lists ** Association Lists in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] #+BEGIN_SRC ocaml exception MissingKey of string #+END_SRC #+RESULTS: : exception MissingKey of string *** Lookup Lookup has time complexity $O(n)$ #+BEGIN_SRC ocaml let rec lookup key = function | [] -> raise (MissingKey key) | (key' , value) :: rest -> if key = key' then value else lookup key rest #+END_SRC #+RESULTS: : <fun> *** Update Update has time complexity $O(1)$ Update has space complexity $O(n)$ where $n$ is the number of insertions. Note that update may have non-optimal space complexity because old keys are not removed. #+BEGIN_SRC ocaml let update key value = List.cons (key , value ) #+END_SRC #+RESULTS: : <fun>