1041 Intermediate

1041-multimap — Multimap

Functional Programming

Tutorial

The Problem

A multimap (or multi-dictionary) maps each key to multiple values. Real-world examples: a person can have multiple phone numbers, a web server can handle multiple routes for the same path prefix, a product can belong to multiple categories. Standard hash maps do not support this — inserting the same key twice overwrites the old value.

The canonical Rust implementation uses HashMap<K, Vec<V>> as the underlying storage. This example wraps it in a MultiMap<K, V> struct providing ergonomic insert, get (returning a slice), and count operations.

🎯 Learning Outcomes

• Implement MultiMap<K, V> using HashMap<K, Vec<V>>

• Use the Entry API for efficient multi-value insert

• Provide get(&key) -> &[V] returning a slice for zero-copy access

• Implement removal of a specific value from a key's value list

• Understand when multimap crate variants are preferred over custom implementations

Code Example

#![allow(clippy::all)]
// 1041: Multimap — HashMap<K, Vec<V>> with Helpers
// A map where each key can have multiple values

use std::collections::HashMap;

/// A multimap: each key maps to a Vec of values
struct MultiMap<K, V> {
    inner: HashMap<K, Vec<V>>,
}

impl<K: std::hash::Hash + Eq, V> MultiMap<K, V> {
    fn new() -> Self {
        MultiMap {
            inner: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) {
        self.inner.entry(key).or_default().push(value);
    }

    fn get(&self, key: &K) -> &[V] {
        self.inner.get(key).map_or(&[], |v| v.as_slice())
    }

    fn remove_key(&mut self, key: &K) -> Option<Vec<V>> {
        self.inner.remove(key)
    }

    fn count_values(&self, key: &K) -> usize {
        self.get(key).len()
    }

    fn total_values(&self) -> usize {
        self.inner.values().map(|v| v.len()).sum()
    }

    fn keys(&self) -> impl Iterator<Item = &K> {
        self.inner.keys()
    }

    fn contains_key(&self, key: &K) -> bool {
        self.inner.contains_key(key)
    }
}

impl<K: std::hash::Hash + Eq, V: PartialEq> MultiMap<K, V> {
    fn remove_value(&mut self, key: &K, value: &V) -> bool {
        if let Some(values) = self.inner.get_mut(key) {
            if let Some(pos) = values.iter().position(|v| v == value) {
                values.remove(pos);
                if values.is_empty() {
                    self.inner.remove(key);
                }
                return true;
            }
        }
        false
    }

    fn contains_value(&self, key: &K, value: &V) -> bool {
        self.get(key).contains(value)
    }
}

fn basic_ops() {
    let mut mm = MultiMap::new();
    mm.insert("fruits", "apple");
    mm.insert("fruits", "banana");
    mm.insert("fruits", "cherry");
    mm.insert("vegs", "carrot");
    mm.insert("vegs", "pea");

    assert_eq!(mm.get(&"fruits"), &["apple", "banana", "cherry"]);
    assert_eq!(mm.get(&"vegs"), &["carrot", "pea"]);
    assert_eq!(mm.count_values(&"fruits"), 3);
    assert_eq!(mm.total_values(), 5);
}

fn remove_ops() {
    let mut mm = MultiMap::new();
    mm.insert("tags", "rust");
    mm.insert("tags", "ocaml");
    mm.insert("tags", "haskell");

    assert!(mm.remove_value(&"tags", &"ocaml"));
    assert_eq!(mm.get(&"tags"), &["rust", "haskell"]);

    mm.remove_key(&"tags");
    assert_eq!(mm.get(&"tags"), &[] as &[&str]);
}

fn build_index() {
    let data = vec![
        ("lang", "Rust"),
        ("lang", "OCaml"),
        ("lang", "Haskell"),
        ("paradigm", "functional"),
        ("paradigm", "imperative"),
    ];

    let mut mm = MultiMap::new();
    for (key, value) in data {
        mm.insert(key, value);
    }

    assert_eq!(mm.get(&"lang"), &["Rust", "OCaml", "Haskell"]);
    assert_eq!(mm.get(&"paradigm"), &["functional", "imperative"]);
    assert!(mm.contains_value(&"lang", &"Rust"));
    assert!(!mm.contains_value(&"lang", &"Python"));
}

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

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_remove() {
        remove_ops();
    }

    #[test]
    fn test_index() {
        build_index();
    }

    #[test]
    fn test_empty_get() {
        let mm: MultiMap<&str, i32> = MultiMap::new();
        assert_eq!(mm.get(&"missing"), &[] as &[i32]);
        assert_eq!(mm.count_values(&"missing"), 0);
    }
}

(* 1041: Multimap — HashMap<K, Vec<V>> with Helpers *)
(* A map where each key maps to multiple values *)

module StringMap = Map.Make(String)

type 'a multimap = 'a list StringMap.t

let empty : 'a multimap = StringMap.empty

let add key value (mm : 'a multimap) : 'a multimap =
  let current = match StringMap.find_opt key mm with
    | Some vs -> vs
    | None -> []
  in
  StringMap.add key (current @ [value]) mm

let get key (mm : 'a multimap) : 'a list =
  match StringMap.find_opt key mm with
  | Some vs -> vs
  | None -> []

let remove_key key (mm : 'a multimap) : 'a multimap =
  StringMap.remove key mm

let remove_value key value (mm : 'a multimap) : 'a multimap =
  match StringMap.find_opt key mm with
  | None -> mm
  | Some vs ->
    let filtered = List.filter (fun v -> v <> value) vs in
    if filtered = [] then StringMap.remove key mm
    else StringMap.add key filtered mm

let count_values key (mm : 'a multimap) : int =
  List.length (get key mm)

let total_values (mm : 'a multimap) : int =
  StringMap.fold (fun _ vs acc -> acc + List.length vs) mm 0

(* Approach 1: Basic multimap operations *)
let basic_ops () =
  let mm = empty
    |> add "fruits" "apple"
    |> add "fruits" "banana"
    |> add "fruits" "cherry"
    |> add "vegs" "carrot"
    |> add "vegs" "pea"
  in
  assert (get "fruits" mm = ["apple"; "banana"; "cherry"]);
  assert (get "vegs" mm = ["carrot"; "pea"]);
  assert (count_values "fruits" mm = 3);
  assert (total_values mm = 5)

(* Approach 2: Remove operations *)
let remove_ops () =
  let mm = empty
    |> add "tags" "rust"
    |> add "tags" "ocaml"
    |> add "tags" "haskell"
  in
  let mm = remove_value "tags" "ocaml" mm in
  assert (get "tags" mm = ["rust"; "haskell"]);
  let mm = remove_key "tags" mm in
  assert (get "tags" mm = [])

(* Approach 3: Index building *)
let build_index items =
  List.fold_left (fun mm (key, value) ->
    add key value mm
  ) empty items

let index_test () =
  let data = [
    ("lang", "Rust"); ("lang", "OCaml"); ("lang", "Haskell");
    ("paradigm", "functional"); ("paradigm", "imperative");
  ] in
  let mm = build_index data in
  assert (get "lang" mm = ["Rust"; "OCaml"; "Haskell"]);
  assert (get "paradigm" mm = ["functional"; "imperative"])

let () =
  basic_ops ();
  remove_ops ();
  index_test ();
  Printf.printf "✓ All tests passed\n"

Key Differences

Persistence: OCaml's map-of-lists is persistent (insert returns new map); Rust's HashMap<K, Vec<V>> mutates in place.

Slice API: Rust's get returns &[V] — a zero-copy view; OCaml's find returns the list by value.

Entry API: Rust's or_default().push() is one lookup; OCaml requires two operations (find + add).

Library support: The multimap crate and indexmap::IndexMap provide production-ready multimaps; OCaml's Base.Map.add_multi is the stdlib equivalent.

OCaml Approach

OCaml's functional multimap uses a persistent map of lists:

module StringMultiMap = Map.Make(String)

let insert key value m =
  let values = try StringMultiMap.find key m with Not_found -> [] in
  StringMultiMap.add key (value :: values) m

let get key m =
  try StringMultiMap.find key m with Not_found -> []

Each insert creates a new map version. The Base.Map.add_multi function provides this in one call.

Full Source

#![allow(clippy::all)]
// 1041: Multimap — HashMap<K, Vec<V>> with Helpers
// A map where each key can have multiple values

use std::collections::HashMap;

/// A multimap: each key maps to a Vec of values
struct MultiMap<K, V> {
    inner: HashMap<K, Vec<V>>,
}

impl<K: std::hash::Hash + Eq, V> MultiMap<K, V> {
    fn new() -> Self {
        MultiMap {
            inner: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) {
        self.inner.entry(key).or_default().push(value);
    }

    fn get(&self, key: &K) -> &[V] {
        self.inner.get(key).map_or(&[], |v| v.as_slice())
    }

    fn remove_key(&mut self, key: &K) -> Option<Vec<V>> {
        self.inner.remove(key)
    }

    fn count_values(&self, key: &K) -> usize {
        self.get(key).len()
    }

    fn total_values(&self) -> usize {
        self.inner.values().map(|v| v.len()).sum()
    }

    fn keys(&self) -> impl Iterator<Item = &K> {
        self.inner.keys()
    }

    fn contains_key(&self, key: &K) -> bool {
        self.inner.contains_key(key)
    }
}

impl<K: std::hash::Hash + Eq, V: PartialEq> MultiMap<K, V> {
    fn remove_value(&mut self, key: &K, value: &V) -> bool {
        if let Some(values) = self.inner.get_mut(key) {
            if let Some(pos) = values.iter().position(|v| v == value) {
                values.remove(pos);
                if values.is_empty() {
                    self.inner.remove(key);
                }
                return true;
            }
        }
        false
    }

    fn contains_value(&self, key: &K, value: &V) -> bool {
        self.get(key).contains(value)
    }
}

fn basic_ops() {
    let mut mm = MultiMap::new();
    mm.insert("fruits", "apple");
    mm.insert("fruits", "banana");
    mm.insert("fruits", "cherry");
    mm.insert("vegs", "carrot");
    mm.insert("vegs", "pea");

    assert_eq!(mm.get(&"fruits"), &["apple", "banana", "cherry"]);
    assert_eq!(mm.get(&"vegs"), &["carrot", "pea"]);
    assert_eq!(mm.count_values(&"fruits"), 3);
    assert_eq!(mm.total_values(), 5);
}

fn remove_ops() {
    let mut mm = MultiMap::new();
    mm.insert("tags", "rust");
    mm.insert("tags", "ocaml");
    mm.insert("tags", "haskell");

    assert!(mm.remove_value(&"tags", &"ocaml"));
    assert_eq!(mm.get(&"tags"), &["rust", "haskell"]);

    mm.remove_key(&"tags");
    assert_eq!(mm.get(&"tags"), &[] as &[&str]);
}

fn build_index() {
    let data = vec![
        ("lang", "Rust"),
        ("lang", "OCaml"),
        ("lang", "Haskell"),
        ("paradigm", "functional"),
        ("paradigm", "imperative"),
    ];

    let mut mm = MultiMap::new();
    for (key, value) in data {
        mm.insert(key, value);
    }

    assert_eq!(mm.get(&"lang"), &["Rust", "OCaml", "Haskell"]);
    assert_eq!(mm.get(&"paradigm"), &["functional", "imperative"]);
    assert!(mm.contains_value(&"lang", &"Rust"));
    assert!(!mm.contains_value(&"lang", &"Python"));
}

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

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_remove() {
        remove_ops();
    }

    #[test]
    fn test_index() {
        build_index();
    }

    #[test]
    fn test_empty_get() {
        let mm: MultiMap<&str, i32> = MultiMap::new();
        assert_eq!(mm.get(&"missing"), &[] as &[i32]);
        assert_eq!(mm.count_values(&"missing"), 0);
    }
}

(* 1041: Multimap — HashMap<K, Vec<V>> with Helpers *)
(* A map where each key maps to multiple values *)

module StringMap = Map.Make(String)

type 'a multimap = 'a list StringMap.t

let empty : 'a multimap = StringMap.empty

let add key value (mm : 'a multimap) : 'a multimap =
  let current = match StringMap.find_opt key mm with
    | Some vs -> vs
    | None -> []
  in
  StringMap.add key (current @ [value]) mm

let get key (mm : 'a multimap) : 'a list =
  match StringMap.find_opt key mm with
  | Some vs -> vs
  | None -> []

let remove_key key (mm : 'a multimap) : 'a multimap =
  StringMap.remove key mm

let remove_value key value (mm : 'a multimap) : 'a multimap =
  match StringMap.find_opt key mm with
  | None -> mm
  | Some vs ->
    let filtered = List.filter (fun v -> v <> value) vs in
    if filtered = [] then StringMap.remove key mm
    else StringMap.add key filtered mm

let count_values key (mm : 'a multimap) : int =
  List.length (get key mm)

let total_values (mm : 'a multimap) : int =
  StringMap.fold (fun _ vs acc -> acc + List.length vs) mm 0

(* Approach 1: Basic multimap operations *)
let basic_ops () =
  let mm = empty
    |> add "fruits" "apple"
    |> add "fruits" "banana"
    |> add "fruits" "cherry"
    |> add "vegs" "carrot"
    |> add "vegs" "pea"
  in
  assert (get "fruits" mm = ["apple"; "banana"; "cherry"]);
  assert (get "vegs" mm = ["carrot"; "pea"]);
  assert (count_values "fruits" mm = 3);
  assert (total_values mm = 5)

(* Approach 2: Remove operations *)
let remove_ops () =
  let mm = empty
    |> add "tags" "rust"
    |> add "tags" "ocaml"
    |> add "tags" "haskell"
  in
  let mm = remove_value "tags" "ocaml" mm in
  assert (get "tags" mm = ["rust"; "haskell"]);
  let mm = remove_key "tags" mm in
  assert (get "tags" mm = [])

(* Approach 3: Index building *)
let build_index items =
  List.fold_left (fun mm (key, value) ->
    add key value mm
  ) empty items

let index_test () =
  let data = [
    ("lang", "Rust"); ("lang", "OCaml"); ("lang", "Haskell");
    ("paradigm", "functional"); ("paradigm", "imperative");
  ] in
  let mm = build_index data in
  assert (get "lang" mm = ["Rust"; "OCaml"; "Haskell"]);
  assert (get "paradigm" mm = ["functional"; "imperative"])

let () =
  basic_ops ();
  remove_ops ();
  index_test ();
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_basic() {
        basic_ops();
    }

    #[test]
    fn test_remove() {
        remove_ops();
    }

    #[test]
    fn test_index() {
        build_index();
    }

    #[test]
    fn test_empty_get() {
        let mm: MultiMap<&str, i32> = MultiMap::new();
        assert_eq!(mm.get(&"missing"), &[] as &[i32]);
        assert_eq!(mm.count_values(&"missing"), 0);
    }
}

Deep Comparison

Multimap — Comparison

Core Insight

A multimap (one key → many values) is a thin wrapper over a map-to-list/vec. Both languages build it the same way — the difference is ergonomics. Rust's Entry API makes insertion clean; OCaml requires explicit find-or-create.

OCaml Approach

• 'a list StringMap.t — map to list of values

• add: find_opt + append + add

• remove_value: filter + conditional remove

• Immutable — each operation returns new multimap

• Module functions operate on the type alias

Rust Approach

• HashMap<K, Vec<V>> wrapped in a struct

• entry().or_default().push() for insertion

• remove_value: find + position + remove

• Separate impl block for V: PartialEq operations

• map_or(&[], ...) for safe empty access

Comparison Table

Feature	OCaml	Rust
Type	`'a list Map.t`	`HashMap<K, Vec<V>>`
Insert	`find_opt` + append + `add`	`entry().or_default().push()`
Get	`find_opt` / default `[]`	`get().map_or(&[], ...)`
Remove value	`filter` + conditional remove	`position` + `remove`
Mutability	Immutable	Mutable
Trait bounds	`Ord` (Map functor)	`Hash + Eq` (HashMap)

Exercises

Add remove_value(&mut self, key: &K, value: &V) that removes one specific value from a key, keeping other values.

Implement values_flat(&self) -> impl Iterator<Item=&V> that iterates all values across all keys.

Write invert<K, V>(m: &MultiMap<K, V>) -> MultiMap<V, K> that inverts the multimap, mapping each value back to its keys.

Open Source Repos

functional-rust

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

Rust