ExamplesBy LevelBy TopicLearning Paths
933 Fundamental
← 932934 →

933-map-functor — Map / Functor

Functional Programming

Tutorial

The Problem

A balanced binary search tree map (dictionary) is one of the most important data structures in functional programming: O(log n) insert, lookup, and delete with ordered iteration. OCaml's Map.Make functor instantiates a BST map for any totally-ordered key type — this is a module-level generic. Rust uses BTreeMap<K, V> where K: Ord serves the same role with generics. The key contrast: OCaml's functor approach allows creating map modules specialized to a key type at the module level; Rust's generics parameterize at the function/struct level. Both produce efficient ordered maps with similar APIs.

🎯 Learning Outcomes

  • • Use BTreeMap<K, V> for ordered key-value mapping (equivalent to OCaml's Map.Make)
  • • Use HashMap<K, V> for O(1) average lookup (equivalent to OCaml's Hashtbl)
  • • Implement functional map operations: filter_by_value, map_values
  • • Understand the BTreeMap/HashMap trade-off (order vs performance)
  • • Compare Rust's generics with OCaml's Map.Make functor for parameterized maps

    • Code Example

    #![allow(clippy::all)]
/// Map.Make Functor — String→Int Dictionary
///
/// OCaml's `Map.Make(String)` creates a specialized balanced BST map.
/// Rust's `std::collections::BTreeMap` and `HashMap` serve the same role.
/// The key difference: OCaml uses functors (module-level functions) to
/// parameterize the map by key type; Rust uses generics with trait bounds.
use std::collections::BTreeMap;

/// Build a word-length map using BTreeMap (ordered, like OCaml's Map).
pub fn word_lengths(words: &[&str]) -> BTreeMap<String, usize> {
    words.iter().map(|w| (w.to_string(), w.len())).collect()
}

/// Filter entries by a predicate on values.
pub fn filter_by_value<K: Ord + Clone, V: Clone>(
    map: &BTreeMap<K, V>,
    pred: impl Fn(&V) -> bool,
) -> BTreeMap<K, V> {
    map.iter()
        .filter(|(_, v)| pred(v))
        .map(|(k, v)| (k.clone(), v.clone()))
        .collect()
}

/// Map over values, producing a new map.
pub fn map_values<K: Ord + Clone, V, U>(
    map: &BTreeMap<K, V>,
    f: impl Fn(&V) -> U,
) -> BTreeMap<K, U> {
    map.iter().map(|(k, v)| (k.clone(), f(v))).collect()
}

/// Using HashMap for O(1) average lookup (unordered).
use std::collections::HashMap;

pub fn word_lengths_hash(words: &[&str]) -> HashMap<String, usize> {
    words.iter().map(|w| (w.to_string(), w.len())).collect()
}

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

    #[test]
    fn test_word_lengths() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        assert_eq!(m.get("rust"), Some(&4));
        assert_eq!(m.get("haskell"), Some(&7));
        assert_eq!(m.get("missing"), None);
    }

    #[test]
    fn test_filter() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        let long = filter_by_value(&m, |v| *v > 4);
        assert_eq!(long.len(), 3); // ocaml(5), haskell(7), erlang(6)
        assert!(long.contains_key("haskell"));
        assert!(!long.contains_key("go"));
    }

    #[test]
    fn test_map_values() {
        let words = vec!["rust", "go"];
        let m = word_lengths(&words);
        let doubled = map_values(&m, |v| v * 2);
        assert_eq!(doubled.get("rust"), Some(&8));
        assert_eq!(doubled.get("go"), Some(&4));
    }

    #[test]
    fn test_empty() {
        let m = word_lengths(&[]);
        assert!(m.is_empty());
    }

    #[test]
    fn test_hash_map() {
        let words = vec!["rust", "go"];
        let m = word_lengths_hash(&words);
        assert_eq!(m.get("rust"), Some(&4));
    }

    #[test]
    fn test_btree_ordering() {
        let words = vec!["zebra", "apple", "mango"];
        let m = word_lengths(&words);
        let keys: Vec<_> = m.keys().collect();
        assert_eq!(keys, vec!["apple", "mango", "zebra"]); // sorted
    }
}

    Key Differences

  • Functor vs generics: OCaml's Map.Make(String) creates a specialized module type; Rust's BTreeMap<String, V> uses type-level generics — both achieve parameterized maps.
  • Ordering requirement: Both require total ordering on keys: Rust uses the Ord trait, OCaml's functor requires a compare function.
  • Immutability: OCaml maps are immutable — Map.add returns a new map; Rust BTreeMap is mutable — .insert modifies in place.
  • Type-level specialization: OCaml functors can specialize the comparison logic (case-insensitive keys, etc.) at module creation; Rust requires implementing Ord on the key type.

    • OCaml Approach

    module StringMap = Map.Make(String) creates a specialized map type. StringMap.empty, StringMap.add key value map, StringMap.find key map, StringMap.filter pred map, StringMap.map f map. OCaml's Map.Make is a functor — it takes a module with type t and compare: t -> t -> int and returns a full map module. This is a module-level generic, more powerful than Rust's type-level generics (it can specialize the comparison semantics at module creation time).

    Full Source

    #![allow(clippy::all)]
/// Map.Make Functor — String→Int Dictionary
///
/// OCaml's `Map.Make(String)` creates a specialized balanced BST map.
/// Rust's `std::collections::BTreeMap` and `HashMap` serve the same role.
/// The key difference: OCaml uses functors (module-level functions) to
/// parameterize the map by key type; Rust uses generics with trait bounds.
use std::collections::BTreeMap;

/// Build a word-length map using BTreeMap (ordered, like OCaml's Map).
pub fn word_lengths(words: &[&str]) -> BTreeMap<String, usize> {
    words.iter().map(|w| (w.to_string(), w.len())).collect()
}

/// Filter entries by a predicate on values.
pub fn filter_by_value<K: Ord + Clone, V: Clone>(
    map: &BTreeMap<K, V>,
    pred: impl Fn(&V) -> bool,
) -> BTreeMap<K, V> {
    map.iter()
        .filter(|(_, v)| pred(v))
        .map(|(k, v)| (k.clone(), v.clone()))
        .collect()
}

/// Map over values, producing a new map.
pub fn map_values<K: Ord + Clone, V, U>(
    map: &BTreeMap<K, V>,
    f: impl Fn(&V) -> U,
) -> BTreeMap<K, U> {
    map.iter().map(|(k, v)| (k.clone(), f(v))).collect()
}

/// Using HashMap for O(1) average lookup (unordered).
use std::collections::HashMap;

pub fn word_lengths_hash(words: &[&str]) -> HashMap<String, usize> {
    words.iter().map(|w| (w.to_string(), w.len())).collect()
}

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

    #[test]
    fn test_word_lengths() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        assert_eq!(m.get("rust"), Some(&4));
        assert_eq!(m.get("haskell"), Some(&7));
        assert_eq!(m.get("missing"), None);
    }

    #[test]
    fn test_filter() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        let long = filter_by_value(&m, |v| *v > 4);
        assert_eq!(long.len(), 3); // ocaml(5), haskell(7), erlang(6)
        assert!(long.contains_key("haskell"));
        assert!(!long.contains_key("go"));
    }

    #[test]
    fn test_map_values() {
        let words = vec!["rust", "go"];
        let m = word_lengths(&words);
        let doubled = map_values(&m, |v| v * 2);
        assert_eq!(doubled.get("rust"), Some(&8));
        assert_eq!(doubled.get("go"), Some(&4));
    }

    #[test]
    fn test_empty() {
        let m = word_lengths(&[]);
        assert!(m.is_empty());
    }

    #[test]
    fn test_hash_map() {
        let words = vec!["rust", "go"];
        let m = word_lengths_hash(&words);
        assert_eq!(m.get("rust"), Some(&4));
    }

    #[test]
    fn test_btree_ordering() {
        let words = vec!["zebra", "apple", "mango"];
        let m = word_lengths(&words);
        let keys: Vec<_> = m.keys().collect();
        assert_eq!(keys, vec!["apple", "mango", "zebra"]); // sorted
    }
}
    ✓ Tests Rust test suite 
    #[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_word_lengths() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        assert_eq!(m.get("rust"), Some(&4));
        assert_eq!(m.get("haskell"), Some(&7));
        assert_eq!(m.get("missing"), None);
    }

    #[test]
    fn test_filter() {
        let words = vec!["ocaml", "rust", "haskell", "erlang", "go"];
        let m = word_lengths(&words);
        let long = filter_by_value(&m, |v| *v > 4);
        assert_eq!(long.len(), 3); // ocaml(5), haskell(7), erlang(6)
        assert!(long.contains_key("haskell"));
        assert!(!long.contains_key("go"));
    }

    #[test]
    fn test_map_values() {
        let words = vec!["rust", "go"];
        let m = word_lengths(&words);
        let doubled = map_values(&m, |v| v * 2);
        assert_eq!(doubled.get("rust"), Some(&8));
        assert_eq!(doubled.get("go"), Some(&4));
    }

    #[test]
    fn test_empty() {
        let m = word_lengths(&[]);
        assert!(m.is_empty());
    }

    #[test]
    fn test_hash_map() {
        let words = vec!["rust", "go"];
        let m = word_lengths_hash(&words);
        assert_eq!(m.get("rust"), Some(&4));
    }

    #[test]
    fn test_btree_ordering() {
        let words = vec!["zebra", "apple", "mango"];
        let m = word_lengths(&words);
        let keys: Vec<_> = m.keys().collect();
        assert_eq!(keys, vec!["apple", "mango", "zebra"]); // sorted
    }
}

    Deep Comparison

    Map.Make Functor — String→Int Dictionary: OCaml vs Rust

    The Core Insight

    Both languages provide immutable, ordered dictionary types backed by balanced trees. The fascinating difference is how they're parameterized: OCaml uses functors (functions from modules to modules) while Rust uses generics with trait bounds. Same goal, fundamentally different abstraction mechanisms.

    OCaml Approach

    Map.Make(String) is a functor application — it takes the String module (which satisfies the OrderedType signature with a compare function) and produces a new module StringMap with all map operations specialized to string keys. The resulting map is an immutable balanced BST. Operations like add, find_opt, filter, and map all return new maps without mutating the original. This functor pattern is central to OCaml's module system.

    Rust Approach

    Rust's BTreeMap<K, V> is a generic type parameterized by key and value types. The key must implement Ord (for ordering) — this is checked at compile time via trait bounds. Unlike OCaml's functor, you don't create a specialized module; you just use the generic type directly. Rust also offers HashMap<K, V> for O(1) average-case lookups (requires Hash + Eq). Iterator adapters (filter, map, collect) provide the functional transformation style.

    Side-by-Side

    ConceptOCamlRust
    Ordered mapMap.Make(String) functorBTreeMap<String, V> generic
    Hash mapThird-party / Hashtbl (mutable)HashMap<K, V> (in std)
    Key constraintOrderedType signatureOrd trait bound
    ParameterizationFunctor (module → module)Generics (type → type)
    ImmutabilityAll operations return new mapMethods take &self, return new collections
    Lookupfind_opt : key -> 'a t -> 'a option.get(&key) -> Option<&V>

    What Rust Learners Should Notice

  • • BTreeMap is Rust's closest equivalent to OCaml's Map — both are balanced BSTs with O(log n) operations
  • • Rust's .collect() is incredibly powerful — it can build any collection from an iterator, guided by type inference
  • • OCaml functors create new modules at compile time; Rust generics monomorphize at compile time — both are zero-cost
  • • HashMap is usually preferred in Rust for performance unless you need ordered iteration
  • • Rust maps own their keys and values — .get() returns Option<&V> (a borrow), not a copy

    • Further Reading

  • • [The Rust Book — Hash Maps](https://doc.rust-lang.org/book/ch08-03-hash-maps.html)
  • • [Rust std::collections::BTreeMap](https://doc.rust-lang.org/std/collections/struct.BTreeMap.html)
  • • [OCaml Map module](https://ocaml.org/docs/maps)

    • Exercises

  • Implement merge_maps<K: Ord + Clone, V: Clone, F: Fn(V, V) -> V>(a: &BTreeMap<K, V>, b: &BTreeMap<K, V>, combine: F) -> BTreeMap<K, V> that merges duplicate keys using combine.
  • Build a word_frequency_sorted(text: &str) -> Vec<(String, usize)> that returns words sorted by frequency descending, then alphabetically.
  • Implement a bimap<K: Ord + Clone, V: Clone, K2: Ord, V2>(map: &BTreeMap<K, V>, key_fn: F, val_fn: G) -> BTreeMap<K2, V2> that transforms both keys and values.

    • Open Source Repos

    functional-rust

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

    Rust