873 Intermediate

873-associated-types — Associated Types

Functional Programming

Tutorial

The Problem

When a trait operation involves a type that varies per implementation — like the element type of a container, or the output type of an addition — you need a way to express that relationship without making the trait itself generic. Rust's associated types solve this: a trait Container declares type Item, and each implementation specifies what Item is. This avoids the ambiguity of generic traits (where multiple Container<i32> and Container<String> implementations could coexist on the same struct) and makes trait bounds more readable. OCaml's module types use the same idea with type t and type item declarations inside module signatures.

🎯 Learning Outcomes

• Declare and use associated types in Rust traits

• Understand why associated types are preferred over generic trait parameters in many cases

• Implement the same trait for multiple concrete types with different Item types

• Compare Rust associated types with OCaml module type type declarations

• Recognize the pattern in standard library traits like Iterator::Item and Add::Output

Code Example

trait Container {
    type Item;
    fn empty() -> Self;
    fn push(&mut self, item: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
}

impl<T> Container for Stack<T> {
    type Item = T;
    fn empty() -> Self { Stack { items: Vec::new() } }
    fn push(&mut self, item: T) { self.items.push(item); }
    fn pop(&mut self) -> Option<T> { self.items.pop() }
}

module type Container = sig
  type t
  type item
  val empty : t
  val push : item -> t -> t
  val pop : t -> (item * t) option
end

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

Key Differences

Disambiguation: Rust associated types prevent multiple implementations of the same trait on one type (unlike generic trait parameters); OCaml module types achieve the same through module identity.

Constraint syntax: Rust uses where C::Item: Display; OCaml uses with type item = ... or functor application.

Type inference: Rust infers associated types from the impl block; OCaml infers them from module structure.

Standard library integration: Rust's Iterator::Item, Add::Output, Index::Output all use associated types — this pattern is pervasive; OCaml uses it in Map.S, Set.S, etc.

OCaml Approach

OCaml's module type Container = sig type t; type item; val push: item -> t -> t; ... end directly parallels Rust's associated type design. A stack module Stack: Container with type item = int fixes the item type at instantiation. The with type refinement in OCaml is the equivalent of specifying type Item = i32 in a Rust impl. OCaml module types also support abstract types that become concrete in implementations, just like Rust's associated types.

Full Source

#![allow(clippy::all)]
// Example 079: Associated Types
// OCaml module types → Rust associated types in traits

// === Approach 1: Trait with associated type ===
trait Container {
    type Item;

    fn empty() -> Self;
    fn push(&mut self, item: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
    fn is_empty(&self) -> bool;
    fn size(&self) -> usize;
}

struct Stack<T> {
    items: Vec<T>,
}

impl<T> Container for Stack<T> {
    type Item = T;

    fn empty() -> Self {
        Stack { items: Vec::new() }
    }

    fn push(&mut self, item: T) {
        self.items.push(item);
    }

    fn pop(&mut self) -> Option<T> {
        self.items.pop()
    }

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

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

// === Approach 2: Associated type for output (like Add trait) ===
trait Combinable {
    type Output;
    fn combine(&self, other: &Self) -> Self::Output;
}

#[derive(Debug, Clone)]
struct Point {
    x: f64,
    y: f64,
}

impl Combinable for Point {
    type Output = f64; // distance between points
    fn combine(&self, other: &Self) -> f64 {
        ((self.x - other.x).powi(2) + (self.y - other.y).powi(2)).sqrt()
    }
}

impl Combinable for String {
    type Output = String;
    fn combine(&self, other: &Self) -> String {
        format!("{}{}", self, other)
    }
}

// === Approach 3: Multiple associated types ===
trait Transformer {
    type Input;
    type Output;
    fn transform(&self, input: Self::Input) -> Self::Output;
}

struct StringLength;

impl Transformer for StringLength {
    type Input = String;
    type Output = usize;
    fn transform(&self, input: String) -> usize {
        input.len()
    }
}

struct Doubler;

impl Transformer for Doubler {
    type Input = i32;
    type Output = i32;
    fn transform(&self, input: i32) -> i32 {
        input * 2
    }
}

// Generic function using associated types
fn apply_transform<T: Transformer>(t: &T, input: T::Input) -> T::Output {
    t.transform(input)
}

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

    #[test]
    fn test_stack_operations() {
        let mut s: Stack<i32> = Container::empty();
        assert!(s.is_empty());
        s.push(10);
        s.push(20);
        assert_eq!(s.size(), 2);
        assert_eq!(s.pop(), Some(20));
        assert_eq!(s.pop(), Some(10));
        assert_eq!(s.pop(), None);
        assert!(s.is_empty());
    }

    #[test]
    fn test_string_stack() {
        let mut s: Stack<String> = Container::empty();
        s.push("hello".into());
        s.push("world".into());
        assert_eq!(s.pop(), Some("world".to_string()));
    }

    #[test]
    fn test_point_distance() {
        let p1 = Point { x: 0.0, y: 0.0 };
        let p2 = Point { x: 3.0, y: 4.0 };
        assert!((p1.combine(&p2) - 5.0).abs() < 1e-10);
    }

    #[test]
    fn test_string_combine() {
        let s1 = "foo".to_string();
        let s2 = "bar".to_string();
        assert_eq!(s1.combine(&s2), "foobar");
    }

    #[test]
    fn test_transformers() {
        assert_eq!(apply_transform(&StringLength, "test".into()), 4);
        assert_eq!(apply_transform(&Doubler, 5), 10);
    }
}

(* Example 079: Associated Types *)
(* OCaml module types → Rust associated 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
  val size : t -> int
end

(* Stack implementation *)
module Stack : Container with type item = int = struct
  type item = int
  type t = int list
  let empty = []
  let push x xs = x :: xs
  let pop = function [] -> None | x :: xs -> Some (x, xs)
  let is_empty = function [] -> true | _ -> false
  let size = List.length
end

(* Approach 2: Module type with type output *)
module type Addable = sig
  type t
  type output
  val add : t -> t -> output
end

module IntAdd : Addable with type t = int and type output = int = struct
  type t = int
  type output = int
  let add a b = a + b
end

module FloatAdd : Addable with type t = float and type output = float = struct
  type t = float
  type output = float
  let add a b = a +. b
end

(* Approach 3: Functor with associated output *)
module type Transformer = sig
  type input
  type output
  val transform : input -> output
end

module StringLen : Transformer with type input = string and type output = int = struct
  type input = string
  type output = int
  let transform = String.length
end

(* Tests *)
let () =
  let s = Stack.empty in
  let s = Stack.push 1 s in
  let s = Stack.push 2 s in
  let s = Stack.push 3 s in
  assert (Stack.size s = 3);
  assert (not (Stack.is_empty s));
  (match Stack.pop s with
   | Some (v, rest) ->
     assert (v = 3);
     assert (Stack.size rest = 2)
   | None -> assert false);

  assert (IntAdd.add 3 4 = 7);
  assert (FloatAdd.add 1.5 2.5 = 4.0);
  assert (StringLen.transform "hello" = 5);

  Printf.printf "✓ All tests passed\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_stack_operations() {
        let mut s: Stack<i32> = Container::empty();
        assert!(s.is_empty());
        s.push(10);
        s.push(20);
        assert_eq!(s.size(), 2);
        assert_eq!(s.pop(), Some(20));
        assert_eq!(s.pop(), Some(10));
        assert_eq!(s.pop(), None);
        assert!(s.is_empty());
    }

    #[test]
    fn test_string_stack() {
        let mut s: Stack<String> = Container::empty();
        s.push("hello".into());
        s.push("world".into());
        assert_eq!(s.pop(), Some("world".to_string()));
    }

    #[test]
    fn test_point_distance() {
        let p1 = Point { x: 0.0, y: 0.0 };
        let p2 = Point { x: 3.0, y: 4.0 };
        assert!((p1.combine(&p2) - 5.0).abs() < 1e-10);
    }

    #[test]
    fn test_string_combine() {
        let s1 = "foo".to_string();
        let s2 = "bar".to_string();
        assert_eq!(s1.combine(&s2), "foobar");
    }

    #[test]
    fn test_transformers() {
        assert_eq!(apply_transform(&StringLength, "test".into()), 4);
        assert_eq!(apply_transform(&Doubler, 5), 10);
    }
}

Deep Comparison

Comparison: Associated Types

Container with Associated Type

OCaml:

module type Container = sig
  type t
  type item
  val empty : t
  val push : item -> t -> t
  val pop : t -> (item * t) option
end

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

Rust:

trait Container {
    type Item;
    fn empty() -> Self;
    fn push(&mut self, item: Self::Item);
    fn pop(&mut self) -> Option<Self::Item>;
}

impl<T> Container for Stack<T> {
    type Item = T;
    fn empty() -> Self { Stack { items: Vec::new() } }
    fn push(&mut self, item: T) { self.items.push(item); }
    fn pop(&mut self) -> Option<T> { self.items.pop() }
}

Transformer Pattern

OCaml:

module type Transformer = sig
  type input
  type output
  val transform : input -> output
end

module StringLen : Transformer with type input = string and type output = int = struct
  type input = string
  type output = int
  let transform = String.length
end

Rust:

trait Transformer {
    type Input;
    type Output;
    fn transform(&self, input: Self::Input) -> Self::Output;
}

impl Transformer for StringLength {
    type Input = String;
    type Output = usize;
    fn transform(&self, input: String) -> usize { input.len() }
}

Exercises

Define a Parseable trait with type Error as an associated type, and implement it for i32 and f64 with different error types.

Add a map method to the Container trait using an associated type MappedOutput<U> (hint: this requires generic associated types in Rust 1.65+).

Implement a Graph trait with type Node and type Edge associated types, and a simple adjacency-list graph that satisfies it.

Open Source Repos

functional-rust

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

Rust