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

#![allow(clippy::all)]
// 079: Associated Types
// type Item in trait definitions

// Approach 1: Trait with associated type
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;
}

struct IntStack {
    elements: Vec<i32>,
}

impl Container for IntStack {
    type Item = i32;
    fn new() -> Self {
        IntStack {
            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()
    }
}

struct StringQueue {
    elements: Vec<String>,
}

impl Container for StringQueue {
    type Item = String;
    fn new() -> Self {
        StringQueue {
            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()
    }
}

// Approach 2: Generic function using associated types
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
}

// Approach 3: Custom iterator with associated type
struct RangeIter {
    current: i32,
    stop: i32,
}

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 test_int_stack() {
        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));
    }

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

    #[test]
    fn test_drain() {
        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());
    }

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

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

#![allow(clippy::all)]
// 079: Associated Types
// type Item in trait definitions

// Approach 1: Trait with associated type
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;
}

struct IntStack {
    elements: Vec<i32>,
}

impl Container for IntStack {
    type Item = i32;
    fn new() -> Self {
        IntStack {
            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()
    }
}

struct StringQueue {
    elements: Vec<String>,
}

impl Container for StringQueue {
    type Item = String;
    fn new() -> Self {
        StringQueue {
            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()
    }
}

// Approach 2: Generic function using associated types
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
}

// Approach 3: Custom iterator with associated type
struct RangeIter {
    current: i32,
    stop: i32,
}

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 test_int_stack() {
        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));
    }

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

    #[test]
    fn test_drain() {
        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());
    }

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

(* 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 test_int_stack() {
        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));
    }

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

    #[test]
    fn test_drain() {
        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());
    }

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

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