245 Expert

Cofree Comonad

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Cofree Comonad" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The Cofree comonad is the categorical dual of the Free monad. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The Cofree comonad is the categorical dual of the Free monad. Where Free builds up effects lazily for later interpretation, Cofree builds up a potentially infinite tree of values annotated with a functor at every node. It is the universal comonad: every comonad arises as a coalgebra for some Cofree instance. In Rust, Cofree enables elegant tree-shaped data structures where each node carries both a value and a collection of children described by a functor.

🎯 Learning Outcomes

• Understand Cofree as Cofree f a = (a, f (Cofree f a))

• Implement extract and extend for Cofree

• See how Cofree generalizes rose trees, streams, and annotated ASTs

• Use Cofree to annotate a recursive AST with type information

• Compare Cofree with OCaml's coinductive (lazy) equivalent

Code Example

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

(* Cofree comonad: annotates every node in a structure with a label.
   Cofree f a = a * f (Cofree f a)
   For f = [], this gives rose trees (annotated with a-values at each node) *)

(* Cofree over list = rose tree *)
type 'a rose = Rose of 'a * 'a rose list

let leaf x       = Rose (x, [])
let node x children = Rose (x, children)

(* Comonad operations *)
let extract (Rose (a, _)) = a

let rec extend (Rose (a, children)) f =
  Rose (f (Rose (a, children)), List.map (fun child -> extend child f) children)

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

(* Functor: map over annotations *)
let rec fmap f (Rose (a, children)) =
  Rose (f a, List.map (fmap f) children)

(* Fold: reduce the tree *)
let rec fold f (Rose (a, children)) =
  f a (List.map (fold f) children)

(* Size and depth *)
let size  = fold (fun _ cs -> 1 + List.fold_left ( + ) 0 cs)
let depth = fold (fun _ cs -> 1 + (List.fold_left max 0 cs))
let sum   = fold (fun a cs -> a + List.fold_left ( + ) 0 cs)

let () =
  let t = node 1 [
    node 2 [leaf 4; leaf 5];
    node 3 [leaf 6; node 7 [leaf 8]];
  ] in

  Printf.printf "root   = %d\n" (extract t);
  Printf.printf "size   = %d\n" (size t);
  Printf.printf "depth  = %d\n" (depth t);
  Printf.printf "sum    = %d\n" (sum t);

  let doubled = fmap (fun n -> n * 2) t in
  Printf.printf "root*2 = %d\n" (extract doubled);

  (* extend: annotate each node with its subtree sum *)
  let annotated = extend t sum in
  Printf.printf "subtree sums at root = %d\n" (extract annotated)

Key Differences

Aspect	Rust	OCaml
Recursion breaking	`Box<Cofree<A>>`	`Lazy.t` list
Infinite structures	requires `Rc`/arena tricks	natural with `Lazy.t`
extend cloning	requires `A: Clone + 'static`	no explicit bounds
Functor parameter	baked in as `Vec`	polymorphic over list functor
Coinduction	not native	`codata` via laziness

A fully generic Cofree<F, A> in Rust requires HKT simulation (GATs), making the Vec-specialized version far more practical for most use cases.

OCaml Approach

OCaml's lazy evaluation makes Cofree natural for infinite structures:

type ('f, 'a) cofree = Cofree of 'a * ('f, 'a) cofree list Lazy.t

let extract (Cofree (a, _)) = a

let rec extend f tree =
  let (Cofree (_, children)) = tree in
  Cofree (f tree, lazy (List.map (extend f) (Lazy.force children)))

(* Infinite stream as Cofree over unit functor *)
let rec nats n = Cofree (n, lazy [nats (n + 1)])

OCaml's Lazy.t avoids the need for explicit Box and enables genuinely infinite Cofree structures without stack overflow.

Full Source

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

(* Cofree comonad: annotates every node in a structure with a label.
   Cofree f a = a * f (Cofree f a)
   For f = [], this gives rose trees (annotated with a-values at each node) *)

(* Cofree over list = rose tree *)
type 'a rose = Rose of 'a * 'a rose list

let leaf x       = Rose (x, [])
let node x children = Rose (x, children)

(* Comonad operations *)
let extract (Rose (a, _)) = a

let rec extend (Rose (a, children)) f =
  Rose (f (Rose (a, children)), List.map (fun child -> extend child f) children)

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

(* Functor: map over annotations *)
let rec fmap f (Rose (a, children)) =
  Rose (f a, List.map (fmap f) children)

(* Fold: reduce the tree *)
let rec fold f (Rose (a, children)) =
  f a (List.map (fold f) children)

(* Size and depth *)
let size  = fold (fun _ cs -> 1 + List.fold_left ( + ) 0 cs)
let depth = fold (fun _ cs -> 1 + (List.fold_left max 0 cs))
let sum   = fold (fun a cs -> a + List.fold_left ( + ) 0 cs)

let () =
  let t = node 1 [
    node 2 [leaf 4; leaf 5];
    node 3 [leaf 6; node 7 [leaf 8]];
  ] in

  Printf.printf "root   = %d\n" (extract t);
  Printf.printf "size   = %d\n" (size t);
  Printf.printf "depth  = %d\n" (depth t);
  Printf.printf "sum    = %d\n" (sum t);

  let doubled = fmap (fun n -> n * 2) t in
  Printf.printf "root*2 = %d\n" (extract doubled);

  (* extend: annotate each node with its subtree sum *)
  let annotated = extend t sum in
  Printf.printf "subtree sums at root = %d\n" (extract annotated)

Deep Comparison

OCaml vs Rust: Cofree Comonad

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 Cofree with Option as the functor (making it a potentially-terminated stream).

Use extend to implement a Huffman encoding annotator: label each node with its subtree character frequency.

Implement unfold: S -> (A, Vec<S>) -> Cofree<A> as the Cofree anamorphism (corecursive unfold).

Show that duplicate (the Cofree version of extend id) produces a tree where each node's annotation is the subtree rooted there.

Implement a Cofree-based attribute grammar evaluator: given a grammar tree and inherited/synthesized attribute rules, use extend to compute the attributes in one traversal.

Open Source Repos

functional-rust

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

Rust