079 Intermediate

079 — Associated Types

Functional Programming

Tutorial

The Problem

Define traits with associated types (type Item) to express relationships between a type and its element type without adding an extra type parameter. Implement a Container trait with IntStack and StringQueue, a generic drain_all utility, and a custom RangeIter — comparing with OCaml's module abstract types.

🎯 Learning Outcomes

• Declare type Item inside a trait and use Self::Item in method signatures

• Understand why associated types often replace generic type parameters in traits

• Implement the standard Iterator trait with type Item = i32

• Write generic functions that refer to a container's item type as C::Item

• Map Rust associated types to OCaml with type item = t module refinements

• Recognise when to use associated types versus generic parameters

Code Example

//! 079: Associated Types — `type Item` inside a trait.
//!
//! An associated type expresses that a trait implementor pairs *itself*
//! with one fixed companion type. `Container` holds items of type
//! `Self::Item`; each implementor pins `Item` in its `impl` block.
//!
//! OCaml expresses the same idea with `module type Container = sig type t;
//! type item; … end` and `Container with type item = int` refinements.
//! Rust's associated types are the trait-system analogue: one `Item` per
//! implementor, no extra generic parameter threading through call sites.

/// A sequential container parameterised over its element type.
///
/// `Item` is an associated type: each implementor picks one concrete
/// element type, so callers never spell out a `<T>` parameter.
pub trait Container {
    type Item;
    fn new() -> Self;
    fn push(&mut self, item: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
    fn is_empty(&self) -> bool;
}

/// LIFO stack of `i32`s — `pop` returns the most recently pushed value.
#[derive(Debug, Default)]
pub struct IntStack {
    elements: Vec<i32>,
}

impl Container for IntStack {
    type Item = i32;

    fn new() -> Self {
        Self {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: i32) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<i32> {
        self.elements.pop()
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

/// FIFO queue of owned `String`s — `pop` removes from the front.
#[derive(Debug, Default)]
pub struct StringQueue {
    elements: Vec<String>,
}

impl Container for StringQueue {
    type Item = String;

    fn new() -> Self {
        Self {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: String) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<String> {
        if self.elements.is_empty() {
            None
        } else {
            Some(self.elements.remove(0))
        }
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

/// Drain a container into a `Vec` of its associated `Item` type.
///
/// The return type `Vec<C::Item>` uses the trait's associated type
/// directly — no `<T>` parameter needed, mirroring OCaml's
/// `C.item` projection inside a functor body.
pub fn drain_all<C: Container>(container: &mut C) -> Vec<C::Item> {
    let mut result = Vec::new();
    while let Some(item) = container.pop() {
        result.push(item);
    }
    result
}

/// Half-open integer range iterator `[current, stop)`.
///
/// Implements the standard `Iterator` trait so every adapter
/// (`map`, `filter`, `collect`, …) works out of the box.
#[derive(Debug, Clone, Copy)]
pub struct RangeIter {
    pub current: i32,
    pub stop: i32,
}

impl RangeIter {
    pub fn new(start: i32, stop: i32) -> Self {
        Self {
            current: start,
            stop,
        }
    }
}

impl Iterator for RangeIter {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.stop {
            None
        } else {
            let v = self.current;
            self.current += 1;
            Some(v)
        }
    }
}

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

    #[test]
    fn int_stack_is_lifo() {
        let mut s = IntStack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert!(!s.is_empty());
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.pop(), Some(2));
        assert_eq!(s.pop(), Some(1));
        assert_eq!(s.pop(), None);
        assert!(s.is_empty());
    }

    #[test]
    fn string_queue_is_fifo() {
        let mut q = StringQueue::new();
        q.push("a".into());
        q.push("b".into());
        q.push("c".into());
        assert_eq!(q.pop().as_deref(), Some("a"));
        assert_eq!(q.pop().as_deref(), Some("b"));
        assert_eq!(q.pop().as_deref(), Some("c"));
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn drain_all_returns_vec_of_associated_item() {
        let mut s = IntStack::new();
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(drain_all(&mut s), vec![3, 2, 1]);
        assert!(s.is_empty());

        let mut q = StringQueue::new();
        q.push("x".into());
        q.push("y".into());
        assert_eq!(drain_all(&mut q), vec!["x".to_string(), "y".to_string()]);
    }

    #[test]
    fn range_iter_collects_like_std_range() {
        let items: Vec<i32> = RangeIter::new(0, 5).collect();
        assert_eq!(items, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_composes_with_adapters() {
        let doubled_even: Vec<i32> = RangeIter::new(0, 10)
            .filter(|n| n % 2 == 0)
            .map(|n| n * 2)
            .collect();
        assert_eq!(doubled_even, vec![0, 4, 8, 12, 16]);
    }

    #[test]
    fn empty_range_iter_yields_nothing() {
        let items: Vec<i32> = RangeIter::new(5, 5).collect();
        assert!(items.is_empty());
    }
}

(* 079: Associated Types — OCaml module abstract types *)

(* Approach 1: Module type with associated type *)
module type Container = sig
  type t
  type item
  val empty : t
  val push : item -> t -> t
  val pop : t -> (item * t) option
  val is_empty : t -> bool
end

module IntStack : Container with type item = int = struct
  type t = int list
  type item = int
  let empty = []
  let push x s = x :: s
  let pop = function [] -> None | x :: xs -> Some (x, xs)
  let is_empty = function [] -> true | _ -> false
end

module StringQueue : Container with type item = string = struct
  type t = string list
  type item = string
  let empty = []
  let push x s = s @ [x]
  let pop = function [] -> None | x :: xs -> Some (x, xs)
  let is_empty = function [] -> true | _ -> false
end

(* Approach 2: Iterator-like with associated type *)
module type Iterator = sig
  type t
  type item
  val next : t -> (item * t) option
end

module RangeIter : Iterator with type item = int = struct
  type t = { current: int; stop: int }
  type item = int
  let next r =
    if r.current >= r.stop then None
    else Some (r.current, { r with current = r.current + 1 })
end

let collect_iter (type a) (module I : Iterator with type item = a) init =
  let rec aux acc state =
    match I.next state with
    | None -> List.rev acc
    | Some (item, next) -> aux (item :: acc) next
  in
  aux [] init

(* Tests *)
let () =
  let s = IntStack.push 3 (IntStack.push 2 (IntStack.push 1 IntStack.empty)) in
  assert (not (IntStack.is_empty s));
  (match IntStack.pop s with Some (v, _) -> assert (v = 3) | None -> assert false);
  let q = StringQueue.push "b" (StringQueue.push "a" StringQueue.empty) in
  (match StringQueue.pop q with Some (v, _) -> assert (v = "a") | None -> assert false);
  let range = RangeIter.{ current = 0; stop = 5 } in
  let items = collect_iter (module RangeIter) range in
  assert (items = [0; 1; 2; 3; 4]);
  Printf.printf "✓ All tests passed\n"

Key Differences

Aspect	Rust	OCaml
Syntax	`type Item;` inside `trait`	`type item` inside `module type`
Pinning	`type Item = i32` in `impl`	`with type item = int` constraint
Access	`C::Item`	`C.item`
Standard iterator	`Iterator::Item`	Custom `Iterator` module type
Multiple impls	One `Item` per impl	One `item` per module
Generic alternative	`trait Container<T>`	`module type Container(T)` (functor)

Associated types enforce a one-to-one relationship: a given type can only implement Container once, with one fixed Item. Generic parameters (trait Container<T>) allow multiple implementations. OCaml's module system makes this distinction through opaque vs refined types; Rust encodes it structurally through trait design.

OCaml Approach

OCaml module types achieve the same abstraction: module type Container = sig type t; type item; val empty : t; val push : item -> t -> t; … end. The with type item = int refinement pins the abstract type concretely. Functors parameterised over a Container module use C.item just as Rust uses C::Item. The OCaml approach is more explicit — module types and their refinements are named and composed; Rust traits hide the plumbing inside impl blocks.

Full Source

//! 079: Associated Types — `type Item` inside a trait.
//!
//! An associated type expresses that a trait implementor pairs *itself*
//! with one fixed companion type. `Container` holds items of type
//! `Self::Item`; each implementor pins `Item` in its `impl` block.
//!
//! OCaml expresses the same idea with `module type Container = sig type t;
//! type item; … end` and `Container with type item = int` refinements.
//! Rust's associated types are the trait-system analogue: one `Item` per
//! implementor, no extra generic parameter threading through call sites.

/// A sequential container parameterised over its element type.
///
/// `Item` is an associated type: each implementor picks one concrete
/// element type, so callers never spell out a `<T>` parameter.
pub trait Container {
    type Item;
    fn new() -> Self;
    fn push(&mut self, item: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
    fn is_empty(&self) -> bool;
}

/// LIFO stack of `i32`s — `pop` returns the most recently pushed value.
#[derive(Debug, Default)]
pub struct IntStack {
    elements: Vec<i32>,
}

impl Container for IntStack {
    type Item = i32;

    fn new() -> Self {
        Self {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: i32) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<i32> {
        self.elements.pop()
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

/// FIFO queue of owned `String`s — `pop` removes from the front.
#[derive(Debug, Default)]
pub struct StringQueue {
    elements: Vec<String>,
}

impl Container for StringQueue {
    type Item = String;

    fn new() -> Self {
        Self {
            elements: Vec::new(),
        }
    }

    fn push(&mut self, item: String) {
        self.elements.push(item);
    }

    fn pop(&mut self) -> Option<String> {
        if self.elements.is_empty() {
            None
        } else {
            Some(self.elements.remove(0))
        }
    }

    fn is_empty(&self) -> bool {
        self.elements.is_empty()
    }
}

/// Drain a container into a `Vec` of its associated `Item` type.
///
/// The return type `Vec<C::Item>` uses the trait's associated type
/// directly — no `<T>` parameter needed, mirroring OCaml's
/// `C.item` projection inside a functor body.
pub fn drain_all<C: Container>(container: &mut C) -> Vec<C::Item> {
    let mut result = Vec::new();
    while let Some(item) = container.pop() {
        result.push(item);
    }
    result
}

/// Half-open integer range iterator `[current, stop)`.
///
/// Implements the standard `Iterator` trait so every adapter
/// (`map`, `filter`, `collect`, …) works out of the box.
#[derive(Debug, Clone, Copy)]
pub struct RangeIter {
    pub current: i32,
    pub stop: i32,
}

impl RangeIter {
    pub fn new(start: i32, stop: i32) -> Self {
        Self {
            current: start,
            stop,
        }
    }
}

impl Iterator for RangeIter {
    type Item = i32;

    fn next(&mut self) -> Option<Self::Item> {
        if self.current >= self.stop {
            None
        } else {
            let v = self.current;
            self.current += 1;
            Some(v)
        }
    }
}

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

    #[test]
    fn int_stack_is_lifo() {
        let mut s = IntStack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert!(!s.is_empty());
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.pop(), Some(2));
        assert_eq!(s.pop(), Some(1));
        assert_eq!(s.pop(), None);
        assert!(s.is_empty());
    }

    #[test]
    fn string_queue_is_fifo() {
        let mut q = StringQueue::new();
        q.push("a".into());
        q.push("b".into());
        q.push("c".into());
        assert_eq!(q.pop().as_deref(), Some("a"));
        assert_eq!(q.pop().as_deref(), Some("b"));
        assert_eq!(q.pop().as_deref(), Some("c"));
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn drain_all_returns_vec_of_associated_item() {
        let mut s = IntStack::new();
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(drain_all(&mut s), vec![3, 2, 1]);
        assert!(s.is_empty());

        let mut q = StringQueue::new();
        q.push("x".into());
        q.push("y".into());
        assert_eq!(drain_all(&mut q), vec!["x".to_string(), "y".to_string()]);
    }

    #[test]
    fn range_iter_collects_like_std_range() {
        let items: Vec<i32> = RangeIter::new(0, 5).collect();
        assert_eq!(items, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_composes_with_adapters() {
        let doubled_even: Vec<i32> = RangeIter::new(0, 10)
            .filter(|n| n % 2 == 0)
            .map(|n| n * 2)
            .collect();
        assert_eq!(doubled_even, vec![0, 4, 8, 12, 16]);
    }

    #[test]
    fn empty_range_iter_yields_nothing() {
        let items: Vec<i32> = RangeIter::new(5, 5).collect();
        assert!(items.is_empty());
    }
}

(* 079: Associated Types — OCaml module abstract types *)

(* Approach 1: Module type with associated type *)
module type Container = sig
  type t
  type item
  val empty : t
  val push : item -> t -> t
  val pop : t -> (item * t) option
  val is_empty : t -> bool
end

module IntStack : Container with type item = int = struct
  type t = int list
  type item = int
  let empty = []
  let push x s = x :: s
  let pop = function [] -> None | x :: xs -> Some (x, xs)
  let is_empty = function [] -> true | _ -> false
end

module StringQueue : Container with type item = string = struct
  type t = string list
  type item = string
  let empty = []
  let push x s = s @ [x]
  let pop = function [] -> None | x :: xs -> Some (x, xs)
  let is_empty = function [] -> true | _ -> false
end

(* Approach 2: Iterator-like with associated type *)
module type Iterator = sig
  type t
  type item
  val next : t -> (item * t) option
end

module RangeIter : Iterator with type item = int = struct
  type t = { current: int; stop: int }
  type item = int
  let next r =
    if r.current >= r.stop then None
    else Some (r.current, { r with current = r.current + 1 })
end

let collect_iter (type a) (module I : Iterator with type item = a) init =
  let rec aux acc state =
    match I.next state with
    | None -> List.rev acc
    | Some (item, next) -> aux (item :: acc) next
  in
  aux [] init

(* Tests *)
let () =
  let s = IntStack.push 3 (IntStack.push 2 (IntStack.push 1 IntStack.empty)) in
  assert (not (IntStack.is_empty s));
  (match IntStack.pop s with Some (v, _) -> assert (v = 3) | None -> assert false);
  let q = StringQueue.push "b" (StringQueue.push "a" StringQueue.empty) in
  (match StringQueue.pop q with Some (v, _) -> assert (v = "a") | None -> assert false);
  let range = RangeIter.{ current = 0; stop = 5 } in
  let items = collect_iter (module RangeIter) range in
  assert (items = [0; 1; 2; 3; 4]);
  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn int_stack_is_lifo() {
        let mut s = IntStack::new();
        assert!(s.is_empty());
        s.push(1);
        s.push(2);
        s.push(3);
        assert!(!s.is_empty());
        assert_eq!(s.pop(), Some(3));
        assert_eq!(s.pop(), Some(2));
        assert_eq!(s.pop(), Some(1));
        assert_eq!(s.pop(), None);
        assert!(s.is_empty());
    }

    #[test]
    fn string_queue_is_fifo() {
        let mut q = StringQueue::new();
        q.push("a".into());
        q.push("b".into());
        q.push("c".into());
        assert_eq!(q.pop().as_deref(), Some("a"));
        assert_eq!(q.pop().as_deref(), Some("b"));
        assert_eq!(q.pop().as_deref(), Some("c"));
        assert_eq!(q.pop(), None);
    }

    #[test]
    fn drain_all_returns_vec_of_associated_item() {
        let mut s = IntStack::new();
        s.push(1);
        s.push(2);
        s.push(3);
        assert_eq!(drain_all(&mut s), vec![3, 2, 1]);
        assert!(s.is_empty());

        let mut q = StringQueue::new();
        q.push("x".into());
        q.push("y".into());
        assert_eq!(drain_all(&mut q), vec!["x".to_string(), "y".to_string()]);
    }

    #[test]
    fn range_iter_collects_like_std_range() {
        let items: Vec<i32> = RangeIter::new(0, 5).collect();
        assert_eq!(items, vec![0, 1, 2, 3, 4]);
    }

    #[test]
    fn range_iter_composes_with_adapters() {
        let doubled_even: Vec<i32> = RangeIter::new(0, 10)
            .filter(|n| n % 2 == 0)
            .map(|n| n * 2)
            .collect();
        assert_eq!(doubled_even, vec![0, 4, 8, 12, 16]);
    }

    #[test]
    fn empty_range_iter_yields_nothing() {
        let items: Vec<i32> = RangeIter::new(5, 5).collect();
        assert!(items.is_empty());
    }
}

Deep Comparison

Core Insight

Associated types define a type placeholder inside a trait. Unlike generic params, there's one impl per type (not per type parameter). Iterator has type Item — each iterator produces one specific type.

OCaml Approach

• Module types with abstract types

• type t in signatures serves similar purpose

• Functors for type-parameterized modules

Rust Approach

• type Item; in trait definition

• Implementor specifies: type Item = i32;

• Used in Iterator, Deref, Index, etc.

Comparison Table

Feature	OCaml	Rust
Syntax	`type t` in sig	`type Item;` in trait
Specify	Module implementation	`type Item = Concrete;`
Multiple	Multiple abstract types	Multiple associated types
Example	`module type S = sig type t end`	`trait I { type Item; }`

Exercises

Add a peek method to Container that returns Option<&Self::Item> without removing the item. Implement it for IntStack.

Create a Transformer trait with type Input and type Output, and implement it for a struct that doubles integers.

Write a generic map_container<C, D> function that drains C and pushes transformed items into D, where D::Item = String and C::Item: Display.

Implement a Fibonacci iterator with type Item = u64 using the standard Iterator trait.

In OCaml, write a functor Mapped(C : Container)(F : sig val f : C.item -> C.item end) that applies f to every item during push. Compare the constraint surface with Rust's equivalent generic trait bound.

Open Source Repos

functional-rust

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

Rust