244 Expert

Comonad Laws

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Comonad Laws" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Just as monads must satisfy left identity, right identity, and associativity, comonads must satisfy three dual laws. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Just as monads must satisfy left identity, right identity, and associativity, comonads must satisfy three dual laws. These laws ensure that extract and extend compose predictably, making comonadic abstractions composable and refactorable without hidden surprises. This example formalizes and verifies the comonad laws in Rust using property-based tests on concrete comonad instances.

🎯 Learning Outcomes

• State the three comonad laws precisely: left identity, right identity, and associativity

• Understand each law as the categorical dual of the corresponding monad law

• Write property-based tests that verify the laws hold for Identity, Env, and Store comonads

• Recognize when a candidate extend implementation violates a law

• Connect comonad laws to the coherence conditions of comonadic algebras

Code Example

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

(* Comonad laws (dual of monad laws):
   1. extract . extend f = f
   2. extend extract = id
   3. extend f . extend g = extend (f . extend g)
   
   Verified on the Stream comonad (infinite list with focus) *)

(* Lazy stream *)
type 'a stream = Cons of 'a * (unit -> 'a stream)

let rec from n = Cons (n, fun () -> from (n + 1))
let head (Cons (x, _)) = x
let tail (Cons (_, f)) = f ()

let take n s =
  let rec go n s acc =
    if n = 0 then List.rev acc
    else let Cons (x, f) = s in go (n-1) (f ()) (x :: acc)
  in go n s []

(* Stream is a comonad *)
let extract = head

let rec extend s f =
  Cons (f s, fun () -> extend (tail s) f)

let duplicate s = extend s (fun x -> x)

(* Verify law 1: extract . extend f = f *)
let check_law1 f s =
  let lhs = extract (extend s f) in
  let rhs = f s in
  lhs = rhs

(* Verify law 2: extend extract = id (on first element) *)
let check_law2 s =
  let s' = extend s extract in
  head s = head s'

let () =
  let s = from 1 in

  let f s = head s * 2 in
  assert (check_law1 f s);
  Printf.printf "Law 1 (extract . extend f = f): holds\n";

  assert (check_law2 s);
  Printf.printf "Law 2 (extend extract = id): holds\n";

  (* extend: compute moving average *)
  let avg s = (head s + head (tail s) + head (tail (tail s))) / 3 in
  let avgs = extend s avg in
  Printf.printf "Moving avg of 1..5: [%s]\n"
    (take 5 avgs |> List.map string_of_int |> String.concat ";")

Key Differences

Aspect	Rust	OCaml
Law encoding	unit tests + generics	module signature + qcheck
Trait object limits	`impl Fn` not object-safe	first-class polymorphism
Verification	compile-time + runtime	mostly runtime via qcheck
`PartialEq` constraint	required for equality tests	structural equality built in
Laws as types	not enforceable	not enforceable (same limitation)

Neither language can enforce comonad laws at the type level — they remain runtime-verifiable contracts. This mirrors the situation with monad laws.

OCaml Approach

In OCaml the laws are typically stated as signatures in a functor:

module type COMONAD = sig
  type 'a t
  val extract : 'a t -> 'a
  val extend  : ('a t -> 'b) -> 'a t -> 'b t
  (* Laws (as comments, verified by quickcheck) *)
  (* extend extract = Fun.id *)
  (* extract (extend f x) = f x *)
  (* extend f (extend g x) = extend (fun y -> f (extend g y)) x *)
end

QuickCheck/qcheck handles property verification; Rust uses proptest or hand-written loops.

Full Source

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

(* Comonad laws (dual of monad laws):
   1. extract . extend f = f
   2. extend extract = id
   3. extend f . extend g = extend (f . extend g)
   
   Verified on the Stream comonad (infinite list with focus) *)

(* Lazy stream *)
type 'a stream = Cons of 'a * (unit -> 'a stream)

let rec from n = Cons (n, fun () -> from (n + 1))
let head (Cons (x, _)) = x
let tail (Cons (_, f)) = f ()

let take n s =
  let rec go n s acc =
    if n = 0 then List.rev acc
    else let Cons (x, f) = s in go (n-1) (f ()) (x :: acc)
  in go n s []

(* Stream is a comonad *)
let extract = head

let rec extend s f =
  Cons (f s, fun () -> extend (tail s) f)

let duplicate s = extend s (fun x -> x)

(* Verify law 1: extract . extend f = f *)
let check_law1 f s =
  let lhs = extract (extend s f) in
  let rhs = f s in
  lhs = rhs

(* Verify law 2: extend extract = id (on first element) *)
let check_law2 s =
  let s' = extend s extract in
  head s = head s'

let () =
  let s = from 1 in

  let f s = head s * 2 in
  assert (check_law1 f s);
  Printf.printf "Law 1 (extract . extend f = f): holds\n";

  assert (check_law2 s);
  Printf.printf "Law 2 (extend extract = id): holds\n";

  (* extend: compute moving average *)
  let avg s = (head s + head (tail s) + head (tail (tail s))) / 3 in
  let avgs = extend s avg in
  Printf.printf "Moving avg of 1..5: [%s]\n"
    (take 5 avgs |> List.map string_of_int |> String.concat ";")

Deep Comparison

OCaml vs Rust: Comonad Laws

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

Implement the laws for the Store<usize, i32> comonad using a fixed finite array as the getter.

Find an extend-like operation that satisfies laws 1 and 2 but not 3 (associativity); explain which law breaks and why.

Write a QuickCheck/proptest harness that checks all three laws for Identity<i32> with random values.

Prove algebraically (on paper) that duplicate defined as extend id always satisfies the comonad laws if extend does.

Implement a ComonadLaws<W> trait with associated functions that check all three laws given a sample value, and implement it for both Identity and Env.

Open Source Repos

functional-rust

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

Rust