065 Intermediate

065 — Association List

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "065 — Association List" functional Rust example. Difficulty level: Intermediate. Key concepts covered: Functional Programming. An association list (alist) is the simplest possible key-value store: a list of `(key, value)` pairs where lookup scans from the front and new entries are prepended (shadowing older entries). Key difference from OCaml: 1. **Built

Tutorial

The Problem

An association list (alist) is the simplest possible key-value store: a list of (key, value) pairs where lookup scans from the front and new entries are prepended (shadowing older entries). It is O(1) insert, O(n) lookup, but correct and simple. OCaml and Lisp use alists extensively for environments (variable → value mappings) in interpreters.

Alists are the foundation of lexical scoping: when a new binding is added with insert, it shadows the old binding for the same key — exactly how local variable shadowing works in interpreters. They appear in config overlays, feature flag systems, and small-map scenarios where HashMap overhead is not justified (< 10 entries).

🎯 Learning Outcomes

• Implement insert, lookup, and remove on Vec<(K, V)> using functional patterns

• Understand that prepend (O(1)) shadows existing keys without removing them

• Use iter().find_map() for declarative lookup

• Understand the shadowing semantics: most recently inserted key wins

• Compare alist with HashMap and BTreeMap for different use cases

• Implement Vec<(K, V)> as an association list with O(n) lookup via iter().find(|(k, _)| k == key)

• Understand when alists outperform HashMap: small collections, non-hashable keys, ordered insertion required

Code Example

#![allow(clippy::all)]
/// 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."

Key Differences

Built-in support: OCaml has List.assoc_opt, List.assoc, List.remove_assoc in stdlib. Rust has no alist module; you implement it from Vec or use HashMap.

Shadowing semantics: Both implement shadowing by prepending. OCaml's List.assoc finds the first (most recent) match. Rust's find does the same.

Ownership: Rust's lookup returns Option<&V> — a reference tied to the alist's lifetime. OCaml returns the value directly (GC handles lifetime).

Performance crossover: Alist lookup is O(n). For n > ~10 keys, HashMap is faster. For n < 5, alist avoids hashing overhead. The right choice depends on usage patterns.

**List vs HashMap:** Association lists (alists) are O(n) for lookup. HashMap is O(1) amortized. Alists are used for small collections, configuration (order matters), and when keys are not hashable.

**Vec<(K, V)> in Rust:** The Rust equivalent of an association list is Vec<(K, V)>. Lookup: alist.iter().find(|(k, _)| k == &key).map(|(_, v)| v). OCaml: List.assoc key alist.

First match wins: Both OCaml's List.assoc and a linear scan return the first matching key. This allows "shadowing" — adding a new binding at the front overrides an old one.

**HashMap vs alist:** Use HashMap when the collection is large or lookup frequency is high. Use alist when the collection is small (< 10 items), insertion order matters, or when using it as an immutable persistent map.

OCaml Approach

OCaml's association list: let insert k v lst = (k, v) :: lst. Lookup: List.assoc k lst (raises Not_found) or List.assoc_opt k lst (returns option). Remove: List.remove_assoc k lst. These are all built into OCaml's standard library. The List.assoc_opt function is a recent addition (4.05+); older code uses List.assoc with try/with.

Full Source

#![allow(clippy::all)]
/// 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."

✓ Tests Rust test suite

#[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);
    }
}

Deep 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

Exercises

Env interpreter: Use an alist as the environment in a simple variable-substitution interpreter. eval(env: &[(String, i32)], expr: &Expr) -> i32 where Expr has Var(String) and Const(i32).

Update vs shadow: Write update(k: K, v: V, list: Vec<(K, V)>) -> Vec<(K, V)> that replaces the value for an existing key rather than shadowing. Use iter().map() to transform matching pairs.

To HashMap: Write to_hashmap<K: Eq + Hash, V: Clone>(alist: &[(K, V)]) -> HashMap<K, V> that converts the alist to a HashMap. Note: earlier entries shadow later ones in the alist, so process in reverse order when inserting into the HashMap.

Merge alists: Implement merge_alists<K: Eq + Clone, V: Clone>(a: &[(K, V)], b: &[(K, V)]) -> Vec<(K, V)> that merges two association lists, with entries from a shadowing entries from b for duplicate keys.

Alist to HashMap: Implement alist_to_hashmap<K: Eq + Hash, V>(alist: Vec<(K, V)>) -> HashMap<K, V> and hashmap_to_alist<K: Clone, V: Clone>(map: &HashMap<K, V>) -> Vec<(K, V)>. Note that the alist-to-map conversion discards all but the last value for duplicate keys.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust

Tutorial Video

Tutorial

The Problem

🎯 Learning Outcomes

Code Example

Key Differences

OCaml Approach

Full Source

Deep Comparison

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

The Core Insight

OCaml Approach

Rust Approach

Side-by-Side

What Rust Learners Should Notice

Further Reading

Exercises

Open Source Repos