133: Variance

Difficulty: ⭐⭐⭐ Level: Advanced Understand how Rust's type system decides when one generic type can substitute for another — and how to control it with `PhantomData`.

The Problem This Solves

You have a function that expects a `&'short str` — a string reference valid for a short time. Can you pass a `&'long str` — a reference valid longer? Intuitively yes: something that lives longer is safe to use where something shorter is needed. But what about `&mut Vec<Dog>` where `&mut Vec<Animal>` is expected? That turns out to be unsafe — if the function pushes a `Cat` into `Animal`, your `Vec<Dog>` now contains a Cat. These are variance rules: when can you substitute a type for another in a generic context? The compiler infers variance automatically from how type parameters appear — but when you're working with raw pointers, `PhantomData`, or designing APIs, you may need to control it explicitly. Getting it wrong silently breaks soundness. For API design, variance determines whether a `Producer<Dog>` can be used as a `Producer<Animal>` (covariant — yes, a producer of specific things can produce general things) or whether a `Consumer<Animal>` can be used as a `Consumer<Dog>` (contravariant — yes, something that consumes any animal can consume a dog). Understanding this lets you design correct, flexible APIs.

The Intuition

Covariance: if `Dog` is a subtype of `Animal`, then `Producer<Dog>` is a subtype of `Producer<Animal>`. Producers can be specialized. Think: a function that returns something. It's safe to get back a `Dog` when you expected an `Animal`. Contravariance: `Consumer<Animal>` is a subtype of `Consumer<Dog>`. Consumers can be generalized. Think: a function that accepts something. A function accepting any `Animal` is safe to use where a function accepting a `Dog` is expected — it handles everything dogs do and more. Invariance: neither direction is safe. Mutation creates invariance — if you can read and write, you need the exact type. In Rust, variance is primarily about lifetimes. `&'long T` is covariant in `'long` — a longer lifetime can be used where a shorter one is expected. `&mut T` is invariant in `T` — you can't use `&mut SubType` where `&mut SuperType` is expected, because the function could write a `SuperType` value that breaks the `SubType` guarantee.

How It Works in Rust

use std::marker::PhantomData;

// Variance is controlled by how T appears in PhantomData:

struct Covariant<T> {
 _phantom: PhantomData<T>,        // covariant in T (same as &T)
}

struct Contravariant<T> {
 _phantom: PhantomData<fn(T)>,    // contravariant in T (same as fn(T) -> ())
}

struct Invariant<T> {
 _phantom: PhantomData<fn(T) -> T>,  // invariant in T
}

Practical example — contravariant predicate (can `contramap`):

struct Predicate<T> {
 check: Box<dyn Fn(&T) -> bool>,
}

impl<T: 'static> Predicate<T> {
 // Contramap: given a way to turn U into T, a predicate on T becomes a predicate on U
 // This is the "contravariant functor" — adapt a predicate to a different input type
 fn contramap<U: 'static>(self, f: impl Fn(&U) -> T + 'static) -> Predicate<U> {
     Predicate {
         check: Box::new(move |u| (self.check)(&f(u))),
     }
 }
}

// Usage: adapt an int predicate to work on strings
let is_positive = Predicate::new(|x: &i32| *x > 0);

// A string "has positive length" if its length is positive
// We contramap: provide a way to extract the length (i32) from a String
let has_chars = is_positive.contramap(|s: &String| s.len() as i32);
// has_chars is a Predicate<String>

Practical example — covariant producer (can `map`):

struct Lazy<T> {
 produce: Box<dyn Fn() -> T>,
}

impl<T: 'static> Lazy<T> {
 // Map: transform the output — covariant functor
 fn map<U: 'static>(self, f: impl Fn(T) -> U + 'static) -> Lazy<U> {
     Lazy { produce: Box::new(move || f((self.produce)())) }
 }
}

let int_lazy = Lazy::new(|| 42);
let str_lazy = int_lazy.map(|x| format!("value: {}", x));  // Lazy<String>

What This Unlocks

Correct PhantomData usage — when writing `unsafe` code with raw pointers, choosing the right PhantomData variance prevents the compiler from accepting unsound substitutions.
Functor/contramap patterns — covariant types naturally support `map`; contravariant types support `contramap`; understanding variance tells you which one applies.
Lifetime correctness — variance rules explain why `&mut Vec<&'a str>` is invariant in `'a` and why the borrow checker occasionally needs a nudge via explicit lifetime annotations.

Key Differences

Concept	OCaml	Rust
Variance annotation	Explicit: `type +'a producer`, `type -'a consumer` in type declarations	Inferred from structure; controlled via `PhantomData<T>`, `PhantomData<fn(T)>`
Covariant type	`type +'a producer = { produce : unit -> 'a }`	`PhantomData<T>` or `PhantomData<&'a T>`
Contravariant type	`type -'a consumer = { consume : 'a -> unit }`	`PhantomData<fn(T)>`
Contramap	`let contramap f pred = fun x -> pred (f x)`	`fn contramap<U>(self, f: impl Fn(&U) -> T) -> Predicate<U>`

// Example 133: Variance — Covariance, Contravariance, Invariance
use std::marker::PhantomData;

// Approach 1: Demonstrating variance with lifetimes
// In Rust, variance is primarily about lifetimes:
// - &'a T is covariant in 'a (can shorten lifetime)
// - &'a mut T is invariant in T (cannot substitute)
// - fn(T) is contravariant in T

fn covariant_demo<'a>(long_lived: &'a str) {
    // &'a str is covariant in 'a — a longer lifetime can be used where shorter is expected
    let _short: &str = long_lived; // 'a can shrink to shorter lifetime
}

// Approach 2: PhantomData and variance control
struct Covariant<'a, T> {
    _phantom: PhantomData<&'a T>,  // covariant in both 'a and T
}

struct Contravariant<T> {
    _phantom: PhantomData<fn(T)>,  // contravariant in T
}

struct Invariant<T> {
    _phantom: PhantomData<fn(T) -> T>,  // invariant in T
}

// Approach 3: Practical variance — Producer/Consumer pattern
trait Producer {
    type Item;
    fn produce(&self) -> Self::Item;
}

trait Consumer {
    type Item;
    fn consume(&self, item: Self::Item);
}

struct IntProducer;
impl Producer for IntProducer {
    type Item = i32;
    fn produce(&self) -> i32 { 42 }
}

struct Printer;
impl Consumer for Printer {
    type Item = String;
    fn consume(&self, item: String) { println!("Consumed: {}", item); }
}

// Contramap for predicates (contravariant functor)
struct Predicate<T> {
    check: Box<dyn Fn(&T) -> bool>,
}

impl<T> Predicate<T> {
    fn new(f: impl Fn(&T) -> bool + 'static) -> Self {
        Predicate { check: Box::new(f) }
    }

    fn test(&self, val: &T) -> bool {
        (self.check)(val)
    }
}

impl<T: 'static> Predicate<T> {
    fn contramap<U: 'static>(self, f: impl Fn(&U) -> T + 'static) -> Predicate<U> {
        Predicate {
            check: Box::new(move |u| (self.check)(&f(u))),
        }
    }
}

// Map for producers (covariant functor)
struct Lazy<T> {
    produce: Box<dyn Fn() -> T>,
}

impl<T: 'static> Lazy<T> {
    fn new(f: impl Fn() -> T + 'static) -> Self {
        Lazy { produce: Box::new(f) }
    }

    fn get(&self) -> T {
        (self.produce)()
    }

    fn map<U: 'static>(self, f: impl Fn(T) -> U + 'static) -> Lazy<U> {
        Lazy { produce: Box::new(move || f((self.produce)())) }
    }
}

fn main() {
    // Covariant: Lazy (producer) can map
    let int_lazy = Lazy::new(|| 42);
    let str_lazy = int_lazy.map(|x| format!("value: {}", x));
    println!("{}", str_lazy.get());

    // Contravariant: Predicate can contramap
    let is_positive = Predicate::new(|x: &i32| *x > 0);
    let str_has_chars = is_positive.contramap(|s: &String| s.len() as i32);
    println!("'hello' has chars: {}", str_has_chars.test(&"hello".to_string()));
    println!("'' has chars: {}", str_has_chars.test(&"".to_string()));
}

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

    #[test]
    fn test_covariant_producer() {
        let p = IntProducer;
        assert_eq!(p.produce(), 42);
    }

    #[test]
    fn test_lazy_map() {
        let lazy_int = Lazy::new(|| 10);
        let lazy_str = lazy_int.map(|x| x * 2);
        assert_eq!(lazy_str.get(), 20);
    }

    #[test]
    fn test_predicate_basic() {
        let pred = Predicate::new(|x: &i32| *x > 5);
        assert!(pred.test(&10));
        assert!(!pred.test(&3));
    }

    #[test]
    fn test_predicate_contramap() {
        let is_positive = Predicate::new(|x: &i32| *x > 0);
        let has_length = is_positive.contramap(|s: &String| s.len() as i32);
        assert!(has_length.test(&"hello".to_string()));
        assert!(!has_length.test(&"".to_string()));
    }

    #[test]
    fn test_lifetime_covariance() {
        let owned = String::from("hello");
        covariant_demo(&owned);
    }
}

(* Example 133: Variance — Covariance, Contravariance, Invariance *)

(* Approach 1: Covariance in OCaml *)
(* OCaml infers variance for type parameters *)
type +'a producer = { produce : unit -> 'a }
type -'a consumer = { consume : 'a -> unit }
type 'a invariant_ref = { mutable contents : 'a }

let int_producer : int producer = { produce = fun () -> 42 }

(* Covariance: if int is a subtype via polymorphism, producer is covariant *)
(* OCaml uses structural subtyping with objects/polymorphic variants *)

(* Approach 2: Polymorphic variants show variance *)
type base = [ `A | `B ]
type extended = [ `A | `B | `C ]

(* extended is a subtype of base for covariant positions *)
let use_base (x : base) = match x with `A -> "a" | `B -> "b"
let extended_val : extended = `C

(* Approach 3: Functor variance *)
module type COVARIANT = sig
  type +'a t
  val map : ('a -> 'b) -> 'a t -> 'b t
end

module ListCov : COVARIANT with type 'a t = 'a list = struct
  type 'a t = 'a list
  let map = List.map
end

module type CONTRAVARIANT = sig
  type -'a t
  val contramap : ('b -> 'a) -> 'a t -> 'b t
end

module Predicate : CONTRAVARIANT = struct
  type 'a t = 'a -> bool
  let contramap f pred = fun x -> pred (f x)
end

(* Tests *)
let () =
  assert (int_producer.produce () = 42);
  assert (use_base `A = "a");
  let doubled = ListCov.map (fun x -> x * 2) [1; 2; 3] in
  assert (doubled = [2; 4; 6]);
  let is_positive = fun x -> x > 0 in
  let string_len_positive = Predicate.contramap String.length is_positive in
  assert (string_len_positive "hello" = true);
  assert (string_len_positive "" = false);
  Printf.printf "✓ All tests passed\n"

📊 Detailed Comparison

Comparison: Variance

OCaml

🐪 Show OCaml equivalent

(* Explicit variance annotations *)
type +'a producer = { produce : unit -> 'a }    (* covariant *)
type -'a consumer = { consume : 'a -> unit }    (* contravariant *)
type 'a cell = { mutable contents : 'a }        (* invariant *)

(* Contramap *)
module Predicate = struct
type 'a t = 'a -> bool
let contramap f pred = fun x -> pred (f x)
end

Rust

// Variance controlled by PhantomData shape
struct Covariant<T>(PhantomData<T>);           // covariant
struct Contravariant<T>(PhantomData<fn(T)>);   // contravariant
struct Invariant<T>(PhantomData<fn(T) -> T>);  // invariant

// Contramap
impl<T: 'static> Predicate<T> {
 fn contramap<U: 'static>(self, f: impl Fn(&U) -> T + 'static) -> Predicate<U> {
     Predicate { check: Box::new(move |u| (self.check)(&f(u))) }
 }
}