538 Advanced

Variance: Covariant, Contravariant, Invariant

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Variance: Covariant, Contravariant, Invariant" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Variance describes how subtyping relationships on types propagate through type constructors. Key difference from OCaml: 1. **Automatic inference**: Rust infers variance from how parameters are used (in position, out position, both); OCaml requires explicit `+`/`

Tutorial

The Problem

Variance describes how subtyping relationships on types propagate through type constructors. In Rust's lifetime system: if 'long: 'short (long outlives short), does Container<'long> also satisfy Container<'short> requirements? The answer depends on whether Container is covariant, contravariant, or invariant in its lifetime. Getting variance wrong leads to subtle unsoundness bugs — particularly with mutable references, which must be invariant. Rust computes variance automatically based on how lifetime parameters are used, and PhantomData lets you declare variance for types that need it explicitly.

🎯 Learning Outcomes

• What covariant, contravariant, and invariant mean in terms of lifetime subtyping

• Why &'a T is covariant (longer lifetime usable as shorter)

• Why &'a mut T is invariant (cannot substitute a different lifetime without unsoundness)

• How PhantomData<&'a T> makes a wrapper covariant in 'a

• How PhantomData<&'a mut T> makes a wrapper invariant in 'a

Code Example

// Covariant: &'a T, Box<T>, Vec<T>
// Contravariant: fn(T) -> ()
// Invariant: &'a mut T, Cell<T>

// 'static can be used as shorter lifetime
fn demo<'short>(s: &'static str) -> &'short str { s }

(* Variance annotations in type definitions *)
type +'a covariant = 'a list
type -'a contravariant = 'a -> unit
type 'a invariant = { mutable value: 'a }

Key Differences

Automatic inference: Rust infers variance from how parameters are used (in position, out position, both); OCaml requires explicit +/- annotations or infers from usage.

Lifetime variance: Rust's variance applies to lifetime parameters 'a directly; OCaml has no lifetimes, so variance only applies to type parameters.

Soundness guarantee: Rust's automatic invariance for &mut T prevents a class of memory unsoundness bugs that would be possible with covariant mutable references; OCaml's GC eliminates the corresponding risks.

PhantomData: Rust uses PhantomData to declare variance for types that don't directly store T (e.g., raw pointer wrappers); OCaml achieves the same through direct type parameter annotation.

OCaml Approach

OCaml's type system has variance annotations on type parameters (+'a for covariant, -'a for contravariant, no annotation for invariant). However, these apply to type parameters, not lifetimes, since OCaml has no lifetime system:

type +'a covariant = Cov of 'a   (* covariant in 'a *)
type -'a contravariant = Contra of ('a -> unit)  (* contravariant *)

Full Source

#![allow(clippy::all)]
//! Variance: Covariant, Contravariant, Invariant
//!
//! How subtyping propagates through type constructors.

use std::marker::PhantomData;

/// Covariant wrapper (like &'a T).
pub struct Covariant<'a, T> {
    _marker: PhantomData<&'a T>,
}

/// Invariant wrapper (like &'a mut T).
pub struct Invariant<'a, T> {
    _marker: PhantomData<&'a mut T>,
}

/// Covariant: longer lifetime can be used where shorter expected.
pub fn covariant_demo<'short>(s: &'short str) -> &'short str {
    let long: &'static str = "static";
    // 'static coerces to 'short — covariant
    long
}

/// Demonstrate covariance with Vec.
pub fn vec_covariance<'a>(v: Vec<&'static str>) -> Vec<&'a str> {
    // Vec<&'static T> can coerce to Vec<&'a T> for immutable use
    v
}

/// Cell<T> is invariant in T.
pub fn invariant_example() {
    use std::cell::Cell;
    let cell: Cell<i32> = Cell::new(5);
    cell.set(10);
    assert_eq!(cell.get(), 10);
}

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

    #[test]
    fn test_covariant_demo() {
        let local = String::from("local");
        let result = covariant_demo(&local);
        assert_eq!(result, "static");
    }

    #[test]
    fn test_vec_covariance() {
        let v: Vec<&'static str> = vec!["a", "b", "c"];
        let v2: Vec<&str> = vec_covariance(v);
        assert_eq!(v2.len(), 3);
    }

    #[test]
    fn test_invariant() {
        invariant_example();
    }
}

(* Variance in OCaml — handled by type system automatically *)
(* Covariant type parameter: *)
type 'a box_ = Box of 'a  (* covariant in 'a — safe to use Child where Parent expected *)

(* Contravariant: function argument *)
(* If Animal :> Dog, then (Dog -> unit) :> (Animal -> unit) in OCaml subtyping *)

(* Invariant: mutable references *)
(* ('a ref) is invariant — can't substitute *)

let () =
  (* Covariant example: option is covariant *)
  let x : int option = Some 42 in
  let _ = x in
  Printf.printf "Variance concept: covariant containers are safe for reading\n";
  Printf.printf "Invariant containers (mutable refs) must match exactly\n";
  Printf.printf "Contravariant: functions that ACCEPT base types work where derived expected\n"

✓ Tests Rust test suite

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

    #[test]
    fn test_covariant_demo() {
        let local = String::from("local");
        let result = covariant_demo(&local);
        assert_eq!(result, "static");
    }

    #[test]
    fn test_vec_covariance() {
        let v: Vec<&'static str> = vec!["a", "b", "c"];
        let v2: Vec<&str> = vec_covariance(v);
        assert_eq!(v2.len(), 3);
    }

    #[test]
    fn test_invariant() {
        invariant_example();
    }
}

Deep Comparison

OCaml vs Rust: Variance

OCaml

(* Variance annotations in type definitions *)
type +'a covariant = 'a list
type -'a contravariant = 'a -> unit
type 'a invariant = { mutable value: 'a }

Rust

// Covariant: &'a T, Box<T>, Vec<T>
// Contravariant: fn(T) -> ()
// Invariant: &'a mut T, Cell<T>

// 'static can be used as shorter lifetime
fn demo<'short>(s: &'static str) -> &'short str { s }

Key Differences

OCaml: Variance via +/- annotations on type params

Rust: Variance determined by type structure

Both: Covariant = same direction as subtyping

Both: Contravariant = opposite direction

Both: Invariant = no subtyping allowed

Exercises

Covariant wrapper: Implement struct ReadOnly<'a, T>(PhantomData<&'a T>) and write a function demonstrating a ReadOnly<'static, str> can be used where ReadOnly<'short, str> is expected.

Invariant wrapper: Implement struct Mutable<'a, T>(PhantomData<&'a mut T>) and verify in a comment that substituting 'long for 'short would be rejected by the compiler.

Contravariant usage: Read about PhantomData<fn(T) -> ()> for contravariance and implement a struct Sink<T>(PhantomData<fn(T)>) that is contravariant in T.

Open Source Repos

functional-rust

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

Rust