241 Expert

Comonad Basics

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Comonad Basics" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. A comonad is the categorical dual of a monad. Key difference from OCaml: 1. **Extract vs. pure**: `extract` always succeeds (comonads are "full" containers with at least one element); `pure` always injects (monads can be empty).

Tutorial

The Problem

A comonad is the categorical dual of a monad. Where a monad has pure: A -> M<A> (inject a value) and bind: (A -> M<B>) -> M<A> -> M<B> (sequence effects), a comonad has extract: W<A> -> A (extract the focused value) and extend: (W<A> -> B) -> W<A> -> W<B> (apply a context-dependent function to every position). Comonads model computations that consume context: cellular automata, image processing, signal filtering, and zipper-based navigation.

🎯 Learning Outcomes

• Understand the comonad as the dual of a monad: extract vs. pure, extend vs. bind

• Learn the three comonad operations: extract, duplicate, and extend

• See the NonEmptyVec (with a focused position) as a concrete comonad

• Connect comonads to cellular automata, spreadsheets, and context-dependent computations

Code Example

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

(* Comonads are the dual of monads.
   Monad:   return :: a -> m a    bind :: m a -> (a -> m b) -> m b
   Comonad: extract :: w a -> a   extend :: w a -> (w a -> b) -> w b *)

(* The simplest comonad: Identity *)
type 'a identity = Id of 'a

let extract_id (Id x) = x
let extend_id (Id x) f = Id (f (Id x))
let duplicate_id (Id x) = Id (Id x)

(* Non-empty list (zipper) comonad: focus on current element *)
type 'a zipper = {
  left  : 'a list;   (* elements to the left, reversed *)
  focus : 'a;        (* current focus *)
  right : 'a list;   (* elements to the right *)
}

let make_zipper lst = match lst with
  | []     -> failwith "empty"
  | x :: xs -> { left = []; focus = x; right = xs }

let extract z = z.focus

let move_left z = match z.left with
  | []     -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let move_right z = match z.right with
  | []     -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let extend z f =
  (* Apply f to every possible focus position *)
  let rec go_left z acc =
    let v = f z in
    match move_left z with
    | None -> (v, acc)
    | Some z' -> go_left z' (v :: acc)
  in
  let rec go_right z acc =
    let v = f z in
    match move_right z with
    | None -> (v, acc)
    | Some z' -> go_right z' (acc @ [v])
  in
  let (center, lefts) = go_left z [] in
  let (_, rights) = go_right z [] in
  { left = lefts; focus = center; right = List.tl rights }

let () =
  let z = make_zipper [1; 2; 3; 4; 5] in
  Printf.printf "focus = %d\n" (extract z);

  let z2 = Option.get (move_right z) in
  Printf.printf "after move_right, focus = %d\n" (extract z2);

  (* Comonad law: extract . extend f = f *)
  let f w = w.focus * 2 in
  let extended = extend z f in
  assert (extract extended = f z);
  Printf.printf "extract . extend f = f (law holds)\n"

Key Differences

Extract vs. pure: extract always succeeds (comonads are "full" containers with at least one element); pure always injects (monads can be empty).

Contextual semantics: extend f w computes f at every position of w, using the whole w as context for each position — this is the "cellular automaton" pattern.

Dual laws: Comonad laws are the dual of monad laws; extract (extend f w) = f w mirrors bind return = id.

Practical use: extend is used for image convolution (each pixel computed from a neighborhood), sliding window statistics, and breadcrumb navigation.

OCaml Approach

OCaml's comonad:

module type COMONAD = sig
  type 'a t
  val extract : 'a t -> 'a
  val extend : ('a t -> 'b) -> 'a t -> 'b t
end
module ZipperComonad : COMONAD with type 'a t = 'a zipper = struct
  let extract z = z.focus
  let extend f z = map (fun z' -> f z') (all_positions z)
end

The zipper comonad is the standard OCaml comonad example. Comonads appear in OCaml in data-flow programming and attribute grammars.

Full Source

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

(* Comonads are the dual of monads.
   Monad:   return :: a -> m a    bind :: m a -> (a -> m b) -> m b
   Comonad: extract :: w a -> a   extend :: w a -> (w a -> b) -> w b *)

(* The simplest comonad: Identity *)
type 'a identity = Id of 'a

let extract_id (Id x) = x
let extend_id (Id x) f = Id (f (Id x))
let duplicate_id (Id x) = Id (Id x)

(* Non-empty list (zipper) comonad: focus on current element *)
type 'a zipper = {
  left  : 'a list;   (* elements to the left, reversed *)
  focus : 'a;        (* current focus *)
  right : 'a list;   (* elements to the right *)
}

let make_zipper lst = match lst with
  | []     -> failwith "empty"
  | x :: xs -> { left = []; focus = x; right = xs }

let extract z = z.focus

let move_left z = match z.left with
  | []     -> None
  | x :: xs -> Some { left = xs; focus = x; right = z.focus :: z.right }

let move_right z = match z.right with
  | []     -> None
  | x :: xs -> Some { left = z.focus :: z.left; focus = x; right = xs }

let extend z f =
  (* Apply f to every possible focus position *)
  let rec go_left z acc =
    let v = f z in
    match move_left z with
    | None -> (v, acc)
    | Some z' -> go_left z' (v :: acc)
  in
  let rec go_right z acc =
    let v = f z in
    match move_right z with
    | None -> (v, acc)
    | Some z' -> go_right z' (acc @ [v])
  in
  let (center, lefts) = go_left z [] in
  let (_, rights) = go_right z [] in
  { left = lefts; focus = center; right = List.tl rights }

let () =
  let z = make_zipper [1; 2; 3; 4; 5] in
  Printf.printf "focus = %d\n" (extract z);

  let z2 = Option.get (move_right z) in
  Printf.printf "after move_right, focus = %d\n" (extract z2);

  (* Comonad law: extract . extend f = f *)
  let f w = w.focus * 2 in
  let extended = extend z f in
  assert (extract extended = f z);
  Printf.printf "extract . extend f = f (law holds)\n"

Deep Comparison

OCaml vs Rust: Comonad Basics

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 duplicate: W<A> -> W<W<A>> in terms of extend and verify it gives all focused sub-contexts.

Write a cellular automaton step using extend on Focused<u8>: each cell's next state depends on itself and its two neighbors.

Implement a moving average using extend: each position's value is the average of the 3 surrounding positions.

Open Source Repos

functional-rust

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

Rust