Example 065: Association List — Functional Key-Value Store

Difficulty: ⭐ Category: Data Structures Concept: The simplest functional dictionary: a list of key-value pairs where insert prepends and lookup scans linearly. Shadowing (inserting a duplicate key) naturally works because lookup finds the first match. OCaml → Rust insight: OCaml's list cons `(k,v) :: lst` is O(1) and shares the tail; Rust's `Vec` requires moving all elements, making the ownership cost of "prepend" explicit.

/// Association List — Functional Key-Value Store
///
/// The simplest possible map: a list of (key, value) pairs.
/// Insert prepends (O(1)), lookup scans (O(n)).
/// New entries shadow old ones, just like OCaml's association lists.

/// Insert a key-value pair at the front (shadows any existing key).
pub fn insert<K, V>(k: K, v: V, list: Vec<(K, V)>) -> Vec<(K, V)> {
    let mut new_list = vec![(k, v)];
    new_list.extend(list);
    new_list
}

/// Lookup the first matching key. Returns a reference to the value.
pub fn lookup<'a, K: PartialEq, V>(k: &K, list: &'a [(K, V)]) -> Option<&'a V> {
    list.iter().find(|(key, _)| key == k).map(|(_, v)| v)
}

/// Remove the first occurrence of a key.
pub fn remove<K: PartialEq, V>(k: &K, list: Vec<(K, V)>) -> Vec<(K, V)> {
    let mut found = false;
    list.into_iter()
        .filter(|(key, _)| {
            if !found && key == k {
                found = true;
                false
            } else {
                true
            }
        })
        .collect()
}

/// Get all keys (may contain duplicates due to shadowing).
pub fn keys<K: Clone, V>(list: &[(K, V)]) -> Vec<K> {
    list.iter().map(|(k, _)| k.clone()).collect()
}

/// Iterator-based lookup using `find` — idiomatic Rust.
pub fn lookup_iter<'a, K: PartialEq, V>(k: &K, list: &'a [(K, V)]) -> Option<&'a V> {
    list.iter()
        .find_map(|(key, val)| if key == k { Some(val) } else { None })
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_insert_and_lookup() {
        let d = vec![];
        let d = insert("a", 1, d);
        let d = insert("b", 2, d);
        assert_eq!(lookup(&"a", &d), Some(&1));
        assert_eq!(lookup(&"b", &d), Some(&2));
        assert_eq!(lookup(&"c", &d), None);
    }

    #[test]
    fn test_shadowing() {
        let d = vec![];
        let d = insert("a", 1, d);
        let d = insert("a", 99, d);
        // Latest value shadows
        assert_eq!(lookup(&"a", &d), Some(&99));
    }

    #[test]
    fn test_remove() {
        let d = vec![];
        let d = insert("a", 1, d);
        let d = insert("b", 2, d);
        let d = insert("a", 99, d);
        let d = remove(&"a", d);
        // After removing first "a" (99), the shadowed "a" (1) is visible
        assert_eq!(lookup(&"a", &d), Some(&1));
    }

    #[test]
    fn test_keys() {
        let d = insert("a", 1, insert("b", 2, vec![]));
        assert_eq!(keys(&d), vec!["a", "b"]);
    }

    #[test]
    fn test_empty() {
        let d: Vec<(&str, i32)> = vec![];
        assert_eq!(lookup(&"x", &d), None);
        assert!(keys(&d).is_empty());
    }

    #[test]
    fn test_lookup_iter() {
        let d = insert("x", 42, vec![]);
        assert_eq!(lookup_iter(&"x", &d), Some(&42));
        assert_eq!(lookup_iter(&"y", &d), None);
    }
}

let insert k v lst = (k, v) :: lst

let rec lookup k = function
  | []            -> None
  | (k', v) :: t  -> if k = k' then Some v else lookup k t

let rec remove k = function
  | []                        -> []
  | (k', _) :: t when k = k'  -> t
  | h :: t                    -> h :: remove k t

let keys lst = List.map fst lst

let () =
  let d = [] in
  let d = insert "a" 1 d in
  let d = insert "b" 2 d in
  let d = insert "a" 99 d in
  assert (lookup "a" d = Some 99);
  assert (lookup "c" d = None);
  let d' = remove "a" d in
  assert (lookup "a" d' = Some 1);
  assert (keys d = ["a"; "b"; "a"]);
  print_endline "All assertions passed."

📊 Detailed Comparison

Association List — Functional Key-Value Store: OCaml vs Rust

The Core Insight

Association lists are the "hello world" of functional data structures — just a list of pairs. They reveal how OCaml's persistent linked lists and Rust's owned Vecs handle the same abstraction with very different performance characteristics and ownership semantics.

OCaml Approach

In OCaml, `insert k v lst = (k, v) :: lst` is a single cons operation — O(1) — and the old list is still intact (structural sharing). Lookup with `rec lookup k = function | (k', v) :: t -> ...` is clean pattern matching with O(n) scanning. The `remove` function reconstructs the list up to the matching element. Everything is garbage-collected, so the old list persists as long as anyone references it.

Rust Approach

Rust's `Vec<(K, V)>` owns its elements. Insert at the front requires shifting all elements (O(n)) or we can push to the back and search in reverse. The implementation here uses `vec![(k, v)]` + `extend` for clarity. Lookup returns `Option<&V>` — a borrow, not a copy. The `remove` function consumes the Vec and produces a new one, making ownership transfer explicit. Iterator methods like `find`, `find_map`, and `filter` provide the functional style.

Side-by-Side

Concept	OCaml	Rust
Insert	`(k,v) :: lst` — O(1) cons	`vec![(k,v)]; extend(old)` — O(n)
Lookup	`rec lookup` pattern match	`.iter().find()` — iterator
Remove	Recursive rebuild	`.into_iter().filter().collect()`
Persistence	Free (structural sharing)	Requires cloning
Memory	GC handles sharing	Vec owns all elements
Return type	`'a option`	`Option<&V>` (borrowed)

What Rust Learners Should Notice

OCaml lists are perfect for association lists because cons is O(1) and sharing is free; Rust Vecs don't share, so insert-at-front is expensive
`find_map` is a Rust iterator gem — it combines `find` and `map` in one pass, equivalent to OCaml's recursive pattern match
Rust's `into_iter()` consumes the collection, `iter()` borrows it — choosing correctly is key to ergonomic functional-style code
For real code, use `HashMap` or `BTreeMap` — association lists are pedagogical, not practical for large datasets
The `'a` lifetime in `lookup`'s return type ties the returned reference to the input slice — Rust makes this data dependency explicit