🎬 Traits & Generics Shared behaviour, static vs dynamic dispatch, zero-cost polymorphism.

📝 Text version (for readers / accessibility)

• Traits define shared behaviour — like interfaces but with default implementations

• Generics with trait bounds: fn process(item: T) — monomorphized at compile time

• Static dispatch (impl Trait) = zero cost; dynamic dispatch (dyn Trait) = runtime flexibility via vtable

• Blanket implementations apply traits to all types matching a bound

• Associated types and supertraits enable complex type relationships

143: Associated Type Bounds

Difficulty: 4 Level: Advanced Traits with associated types that carry their own bounds — so generic code can reason about `Key` and `Value` without knowing their concrete types.

The Problem This Solves

Traits with associated types express "this trait has a related type, and different implementors will choose different concrete types." A `Collection` might say "I have a `Key` type." But generic code that works with any `Collection` needs to do something with keys — sort them, print them, compare them. Without bounds on the associated type, none of that is possible. OCaml solves this with module type sharing constraints: `with type key = int` or `with type key = string`. Rust's equivalent is putting trait bounds directly on the associated type: `type Key: Ord + Clone + Display`. Now any generic function that accepts `impl Collection` can call `key1.cmp(&key2)`, `format!("{}", key)`, or `key.clone()` — because the trait guarantees these capabilities regardless of which concrete `Key` type is used. This pattern appears everywhere in real Rust: `std::collections::HashMap`'s key type must be `Hash + Eq`, `BTreeMap`'s must be `Ord`, iterators' `Item` can carry bounds. It's the mechanism that makes generic data structure APIs possible without sacrificing type safety.

The Intuition

Put bounds on a trait's associated type (`type Key: Ord + Clone`) so generic functions working with that trait can use those capabilities without knowing the concrete type.

How It Works in Rust

use std::fmt::{Debug, Display};

pub trait Collection: Sized {
 // Associated types with bounds — any implementor must satisfy these
 type Key: Ord + Clone + Display + Debug;
 type Value: Clone + Debug;

 fn empty() -> Self;
 fn insert(self, key: Self::Key, value: Self::Value) -> Self;
 fn find(&self, key: &Self::Key) -> Option<&Self::Value>;
 fn sorted_keys(&self) -> Vec<Self::Key>;  // possible because Key: Ord
}

// Generic function: works with any Collection
// Can call .sorted_keys() because Key: Ord, format!("{}", key) because Key: Display
fn print_sorted_keys<C: Collection>(coll: &C) {
 let keys = coll.sorted_keys();
 for k in &keys {
     print!("{} ", k);  // works because Key: Display
 }
}

// Another generic function — uses the Value bound
fn lookup_display<C: Collection>(coll: &C, key: &C::Key)
where
 C::Value: Display,  // extra bound on Value for this specific function
{
 match coll.find(key) {
     Some(v) => println!("find({}) = {}", key, v),
     None    => println!("find({}) = not found", key),
 }
}

// Two different implementations with different Key types:
// IntMap<V>:    Key = i32     (implements Collection)
// StringMap<V>: Key = String  (implements Collection)
// Both work with print_sorted_keys — the bounds are what matters, not the type.

let m = IntMap::<&str>::empty().insert(3, "three").insert(1, "one");
print_sorted_keys(&m);   // prints "1 3" — sorted via Ord on i32

let sm = StringMap::<i32>::empty().insert("banana".into(), 3).insert("apple".into(), 1);
print_sorted_keys(&sm);  // prints "apple banana" — sorted via Ord on String

What This Unlocks

Parameterized data structure abstractions — a `Collection` trait that works for any ordered key type, without duplicating code.
Generic algorithms on custom containers — sort, print, merge, diff: any operation that needs `Ord`, `Display`, or `Clone` on keys works once, for all implementors.
OCaml module type analogues — the OCaml `with type key = ...` constraint maps directly to this pattern.

Key Differences

Concept	OCaml	Rust
Constraining associated types	`with type key = int` sharing constraint	`type Key: Ord + Clone + Display` bound
Generic code over any collection	Functor over module type	Generic fn `<C: Collection>`
Multiple key types	Separate modules or functors	Different `impl Collection` blocks
Adding extra bounds per function	Type annotation in signature	`where C::Value: Display` clause

// Associated type bounds: traits with associated types constrained by other traits.
//
// OCaml uses `with type key = int` module sharing constraints.
// Rust uses `type Key: Ord + Clone + Display` in trait definitions —
// the associated type itself carries bounds.
//
// This lets generic code reason about the key type without knowing its concrete form.

use std::fmt::{Debug, Display};

// ── Core Collection trait with bounded associated types ─────────────────────

pub trait Collection: Sized {
    /// The key type must be orderable, cloneable, and printable.
    type Key: Ord + Clone + Display + Debug;
    type Value: Clone + Debug;

    fn empty() -> Self;
    fn insert(self, key: Self::Key, value: Self::Value) -> Self;
    fn find(&self, key: &Self::Key) -> Option<&Self::Value>;
    fn size(&self) -> usize;
    fn is_empty(&self) -> bool { self.size() == 0 }

    /// Remove a key — provided default that rebuilds the collection.
    fn remove(self, key: &Self::Key) -> Self;

    /// Collect all keys in sorted order (thanks to the Ord bound).
    fn sorted_keys(&self) -> Vec<Self::Key>;
}

// ── Integer-keyed map ────────────────────────────────────────────────────────

#[derive(Debug, Clone)]
pub struct IntMap<V> {
    entries: Vec<(i32, V)>,
}

impl<V: Clone + Debug> Collection for IntMap<V> {
    type Key = i32;
    type Value = V;

    fn empty() -> Self { IntMap { entries: Vec::new() } }

    fn insert(mut self, key: i32, value: V) -> Self {
        self.entries.retain(|(k, _)| *k != key);
        self.entries.push((key, value));
        self
    }

    fn find(&self, key: &i32) -> Option<&V> {
        self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
    }

    fn size(&self) -> usize { self.entries.len() }

    fn remove(mut self, key: &i32) -> Self {
        self.entries.retain(|(k, _)| k != key);
        self
    }

    fn sorted_keys(&self) -> Vec<i32> {
        let mut keys: Vec<i32> = self.entries.iter().map(|(k, _)| *k).collect();
        keys.sort();
        keys
    }
}

// ── String-keyed map ─────────────────────────────────────────────────────────

#[derive(Debug, Clone)]
pub struct StringMap<V> {
    entries: Vec<(String, V)>,
}

impl<V: Clone + Debug> Collection for StringMap<V> {
    type Key = String;
    type Value = V;

    fn empty() -> Self { StringMap { entries: Vec::new() } }

    fn insert(mut self, key: String, value: V) -> Self {
        self.entries.retain(|(k, _)| k != &key);
        self.entries.push((key, value));
        self
    }

    fn find(&self, key: &String) -> Option<&V> {
        self.entries.iter().find(|(k, _)| k == key).map(|(_, v)| v)
    }

    fn size(&self) -> usize { self.entries.len() }

    fn remove(mut self, key: &String) -> Self {
        self.entries.retain(|(k, _)| k != key);
        self
    }

    fn sorted_keys(&self) -> Vec<String> {
        let mut keys: Vec<String> = self.entries.iter().map(|(k, _)| k.clone()).collect();
        keys.sort();
        keys
    }
}

// ── Generic functions that work with any Collection ──────────────────────────

/// Print all keys in sorted order — works because Key: Display + Ord.
fn print_sorted_keys<C: Collection>(coll: &C) {
    let keys = coll.sorted_keys();
    let strs: Vec<String> = keys.iter().map(|k| format!("{}", k)).collect();
    println!("  keys (sorted): [{}]", strs.join(", "));
}

/// Look up and display a value.
fn lookup_display<C: Collection>(coll: &C, key: &C::Key)
where
    C::Value: Display,
{
    match coll.find(key) {
        Some(v) => println!("  find({}) = {}", key, v),
        None    => println!("  find({}) = not found", key),
    }
}

/// Merge two collections of the same type (second wins on key conflict).
/// Note: a full implementation would copy values; this shows the type structure.
#[allow(dead_code)]
fn merge_keys<C: Collection>(a: C, b: C) -> Vec<C::Key> {
    let mut keys = a.sorted_keys();
    let bkeys = b.sorted_keys();
    for k in bkeys {
        if !keys.contains(&k) {
            keys.push(k);
        }
    }
    keys.sort();
    keys
}

fn main() {
    // Integer-keyed map
    let m = IntMap::<&str>::empty()
        .insert(2, "two")
        .insert(1, "one")
        .insert(3, "three");

    println!("IntMap size: {}", m.size());
    print_sorted_keys(&m);
    lookup_display(&m, &1);
    lookup_display(&m, &4);

    // Remove a key
    let m2 = m.remove(&2);
    println!("After remove(2), size: {}", m2.size());
    print_sorted_keys(&m2);

    // String-keyed map
    let sm = StringMap::<i32>::empty()
        .insert("banana".to_string(), 3)
        .insert("apple".to_string(), 1)
        .insert("cherry".to_string(), 2);

    println!("StringMap size: {}", sm.size());
    print_sorted_keys(&sm);
    lookup_display(&sm, &"apple".to_string());

    // Generic function: the Key bound lets us sort without knowing the concrete type
    println!("Both maps sorted correctly via the Ord bound on associated type Key.");
}

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

    #[test]
    fn test_int_map_insert_find() {
        let m = IntMap::<&str>::empty()
            .insert(1, "one")
            .insert(2, "two");
        assert_eq!(m.size(), 2);
        assert_eq!(m.find(&1), Some(&"one"));
        assert_eq!(m.find(&3), None);
    }

    #[test]
    fn test_int_map_sorted_keys() {
        let m = IntMap::<i32>::empty()
            .insert(3, 0)
            .insert(1, 0)
            .insert(2, 0);
        assert_eq!(m.sorted_keys(), vec![1, 2, 3]);
    }

    #[test]
    fn test_string_map() {
        let m = StringMap::<i32>::empty()
            .insert("b".to_string(), 2)
            .insert("a".to_string(), 1);
        assert_eq!(m.find(&"a".to_string()), Some(&1));
        assert_eq!(m.sorted_keys(), vec!["a".to_string(), "b".to_string()]);
    }

    #[test]
    fn test_remove() {
        let m = IntMap::<i32>::empty()
            .insert(1, 10)
            .insert(2, 20)
            .remove(&1);
        assert_eq!(m.size(), 1);
        assert_eq!(m.find(&1), None);
    }

    #[test]
    fn test_overwrite() {
        let m = IntMap::<i32>::empty()
            .insert(1, 10)
            .insert(1, 99);
        assert_eq!(m.size(), 1);
        assert_eq!(m.find(&1), Some(&99));
    }
}

(* OCaml's "associated type bounds" are expressed via module type constraints.
   A module type can constrain its type members with :=, with type, or sharing. *)

module type COLLECTION = sig
  type 'a t
  type key
  val empty  : 'a t
  val insert : key -> 'a -> 'a t -> 'a t
  val find   : key -> 'a t -> 'a option
  val size   : 'a t -> int
end

(* Integer-keyed map *)
module IntMap : COLLECTION with type key = int = struct
  type key = int
  type 'a t = (int * 'a) list
  let empty = []
  let insert k v m = (k, v) :: List.filter (fun (k', _) -> k' <> k) m
  let find k m = List.assoc_opt k m
  let size m = List.length m
end

(* String-keyed map *)
module StringMap : COLLECTION with type key = string = struct
  type key = string
  type 'a t = (string * 'a) list
  let empty = []
  let insert k v m = (k, v) :: List.filter (fun (k', _) -> k' <> k) m
  let find k m = List.assoc_opt k m
  let size m = List.length m
end

let () =
  let m = IntMap.(insert 1 "one" (insert 2 "two" empty)) in
  Printf.printf "IntMap size: %d\n" (IntMap.size m);
  (match IntMap.find 1 m with
   | Some v -> Printf.printf "Found: %s\n" v
   | None   -> assert false);

  let sm = StringMap.(insert "a" 1 (insert "b" 2 empty)) in
  Printf.printf "StringMap size: %d\n" (StringMap.size sm)

📊 Detailed Comparison

Comparison: Associated Type Bounds

OCaml

🐪 Show OCaml equivalent

module type KEY = sig
include ORDERED
include PRINTABLE with type t := t
include HASHABLE with type t := t
end

module MakeSortedSet (O : ORDERED) : SORTED_SET with type elt = O.t = struct
(* ... *)
end

Rust

trait Key: Ord + Hash + Display + Debug + Clone {}

fn process<C>(col: &C) -> String
where
 C: Collection,
 C::Item: Display + Debug,
 C::Index: From<usize>,
{ /* ... */ }