150 Advanced

Coherence Rules

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Coherence Rules" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. If two crates independently implement the same trait for the same type, the compiler cannot decide which to use — this is the "coherence problem." Rust's orphan rule prevents this: you can only implement a trait for a type if at least one of the trait or the type is defined in your crate. Key difference from OCaml: 1. **Global coherence**: Rust enforces global coherence at compile time; OCaml relies on convention and explicit passing to avoid incoherence.

Tutorial

The Problem

If two crates independently implement the same trait for the same type, the compiler cannot decide which to use — this is the "coherence problem." Rust's orphan rule prevents this: you can only implement a trait for a type if at least one of the trait or the type is defined in your crate. This guarantees at most one implementation per (Trait, Type) pair globally, making trait resolution unambiguous. Understanding these rules prevents confusing "conflicting implementations" errors.

🎯 Learning Outcomes

• Understand why the orphan rule exists and what problem it solves

• Learn what is allowed: implementing your trait for external types, external traits for your types

• Understand what is forbidden: implementing external traits for external types

• See workarounds: newtype wrapper pattern, blanket implementations

Code Example

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

(* OCaml avoids the Haskell coherence/orphan problem because type class
   instances are just module values, not implicit.
   You explicitly choose which instance to use. *)

(* Semigroup: two implementations of "append" for the same type *)
module type SEMIGROUP = sig
  type t
  val append : t -> t -> t
end

(* Two different semigroup instances for integers *)
module IntSum : SEMIGROUP with type t = int = struct
  type t = int
  let append = ( + )
end

module IntProduct : SEMIGROUP with type t = int = struct
  type t = int
  let append = ( * )
end

(* Explicitly pass the instance — no ambiguity *)
module Fold (S : SEMIGROUP) = struct
  let fold_map f lst =
    match List.map f lst with
    | []     -> failwith "empty list"
    | x :: xs -> List.fold_left S.append x xs
end

module SumFold     = Fold (IntSum)
module ProductFold = Fold (IntProduct)

let () =
  let nums = [1; 2; 3; 4; 5] in
  Printf.printf "sum     = %d\n" (SumFold.fold_map     (fun x -> x) nums);
  Printf.printf "product = %d\n" (ProductFold.fold_map (fun x -> x) nums);

  (* No orphan problem: instances live at module level, chosen explicitly *)
  let concat_strings = Fold (struct
    type t = string
    let append = ( ^ )
  end) in
  Printf.printf "concat  = %s\n" (concat_strings.fold_map (fun x -> x) ["a";"b";"c"])

Key Differences

Global coherence: Rust enforces global coherence at compile time; OCaml relies on convention and explicit passing to avoid incoherence.

Implicit resolution: Rust resolves trait impls globally and implicitly; OCaml passes modules explicitly, so incoherence is visible and manageable.

Orphan workaround: Rust's newtype is the standard orphan workaround; OCaml has no need for it since there is no orphan restriction.

Blanket impls: Rust's blanket impls (impl<T: Trait> OtherTrait for T) are powerful but interact subtly with coherence; OCaml's equivalent (functor application) is always explicit.

OCaml Approach

OCaml has no orphan rule. Any module can implement any type class (module signature) for any type. This can lead to coherence problems in practice — two modules providing different compare functions for the same type. OCaml's solution is convention (use the canonical compare from the standard library) and the functor pattern (pass the implementation explicitly rather than resolving it globally).

Full Source

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

(* OCaml avoids the Haskell coherence/orphan problem because type class
   instances are just module values, not implicit.
   You explicitly choose which instance to use. *)

(* Semigroup: two implementations of "append" for the same type *)
module type SEMIGROUP = sig
  type t
  val append : t -> t -> t
end

(* Two different semigroup instances for integers *)
module IntSum : SEMIGROUP with type t = int = struct
  type t = int
  let append = ( + )
end

module IntProduct : SEMIGROUP with type t = int = struct
  type t = int
  let append = ( * )
end

(* Explicitly pass the instance — no ambiguity *)
module Fold (S : SEMIGROUP) = struct
  let fold_map f lst =
    match List.map f lst with
    | []     -> failwith "empty list"
    | x :: xs -> List.fold_left S.append x xs
end

module SumFold     = Fold (IntSum)
module ProductFold = Fold (IntProduct)

let () =
  let nums = [1; 2; 3; 4; 5] in
  Printf.printf "sum     = %d\n" (SumFold.fold_map     (fun x -> x) nums);
  Printf.printf "product = %d\n" (ProductFold.fold_map (fun x -> x) nums);

  (* No orphan problem: instances live at module level, chosen explicitly *)
  let concat_strings = Fold (struct
    type t = string
    let append = ( ^ )
  end) in
  Printf.printf "concat  = %s\n" (concat_strings.fold_map (fun x -> x) ["a";"b";"c"])

Deep Comparison

OCaml vs Rust: Coherence Rules

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

Demonstrate the orphan rule: try impl Display for Vec<i32> and observe the error, then fix it with a newtype.

Write a blanket implementation impl<T: Clone + Debug> Describable for T and verify it applies to i32, String, and a custom struct.

Implement the same trait for both i32 and a custom type in the same crate and verify the compiler resolves calls correctly.

Open Source Repos

functional-rust

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

Rust