143 Advanced

Associated Type Bounds

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Associated Type Bounds" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. When a trait has associated types, callers often need to constrain those associated types — "give me an iterator whose items are `Clone`" or "give me a container whose element type implements `Display`." Before Rust 1.79, this required verbose `where Item: Clone` clauses in every bound. Key difference from OCaml: 1. **Syntax location**: Rust's associated type bounds are inline in the trait reference; OCaml's `with type` constraints are applied at the module signature level.

Tutorial

The Problem

When a trait has associated types, callers often need to constrain those associated types — "give me an iterator whose items are Clone" or "give me a container whose element type implements Display." Before Rust 1.79, this required verbose where Item: Clone clauses in every bound. Associated type bounds (Iterator<Item: Clone>) compress this into the bound itself, making complex generic signatures readable and reducing repetition in library code.

🎯 Learning Outcomes

• Understand associated types in traits and why they are preferred over type parameters for output types

• Learn the associated type bound syntax Trait<AssocType: Bound> (stabilized in Rust 1.79)

• See how associated type bounds simplify generic function signatures

• Compare with where clauses and understand when each form is clearest

Code Example

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* 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)

Key Differences

Syntax location: Rust's associated type bounds are inline in the trait reference; OCaml's with type constraints are applied at the module signature level.

Expressiveness: Both can express "this associated type must implement this constraint"; Rust's is terser for simple cases, OCaml's is more powerful for complex module constraints.

Inference: Rust infers the concrete associated type from the concrete implementation; OCaml's module system similarly infers types through with type elaboration.

Error messages: Both can produce complex error messages when associated type constraints conflict; Rust 1.79+ improved this significantly with the new bound syntax.

OCaml Approach

OCaml's module system handles associated type constraints via module type constraints:

module type CONTAINER = sig
  type t
  type item
  val items : t -> item list
end
module type DISPLAY_CONTAINER = CONTAINER with type item = string

The with type refinement is OCaml's mechanism for constraining associated types. Functors then take modules satisfying specific refined signatures. This is more verbose than Rust's inline bound syntax but is the standard OCaml pattern.

Full Source

#![allow(clippy::all)]
// Stub — awaiting conversion from OCaml source.

(* 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)

Deep Comparison

OCaml vs Rust: Associated Type Bounds

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Write fn find_max<C: Container<Item: Ord>>(c: C) -> Option<C::Item> using associated type bounds, returning the largest element.

Implement a Mappable trait with type Item and fn map<B>(self, f: impl Fn(Self::Item) -> B) -> Self::Mapped<B> using GATs.

Create fn collect_display<I: Iterator<Item: Display + Clone>>(it: I) -> Vec<String> and test it with vec!["a", "b"].into_iter().

Open Source Repos

functional-rust

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

Rust