242 Expert

Store Comonad

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Store Comonad" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. The Store comonad models a mutable reference into a larger data structure: given a "getter" function and a current focus position, you can read the value at focus, move the focus elsewhere, or derive new stores by transforming the getter. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

The Store comonad models a mutable reference into a larger data structure: given a "getter" function and a current focus position, you can read the value at focus, move the focus elsewhere, or derive new stores by transforming the getter. This captures the essence of how lenses work under the hood. In Rust, implementing Store reveals how comonadic structure enables elegant data-access abstractions without mutation.

🎯 Learning Outcomes

• Understand Store as a pair (s -> a, s) — a getter and a current index

• Implement extract, extend, and duplicate for Store

• See how Store comonad relates to the Lens abstraction

• Explore seek (reposition) and peek (read at arbitrary position)

• Compare Store comonad with OCaml's equivalent using records and closures

Code Example

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

(* Store comonad: models a mutable store.
   Store s a = (s -> a) * s
   extract: read current value
   extend: transform the getter, keeping the store *)

type ('s, 'a) store = Store of ('s -> 'a) * 's

let pos   (Store (_, s)) = s
let peek  (Store (f, _)) s = f s
let extract (Store (f, s)) = f s

let extend (Store (f, s)) g =
  Store ((fun s' -> g (Store (f, s'))), s)

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

(* A 1D cellular automaton via Store comonad! *)
(* The store is: int (position) -> bool (alive/dead), with current focus *)

let make_store arr pos =
  Store ((fun i ->
    let len = Array.length arr in
    let i' = ((i mod len) + len) mod len in
    arr.(i')
  ), pos)

let rule30 store =
  let left  = peek store (pos store - 1) in
  let cur   = extract store in
  let right = peek store (pos store + 1) in
  match (left, cur, right) with
  | (true,  true,  true)  -> false
  | (true,  true,  false) -> false
  | (true,  false, true)  -> false
  | (true,  false, false) -> true
  | (false, true,  true)  -> true
  | (false, true,  false) -> true
  | (false, false, true)  -> true
  | (false, false, false) -> false

let step arr =
  let len = Array.length arr in
  let store = make_store arr 0 in
  Array.init len (fun i ->
    let s = extend store (fun _ -> ()) in
    let s2 = Store ((fun i' ->
      let (Store (f, _)) = store in f i'), i) in
    rule30 s2
  )

let print_gen arr =
  Array.iter (fun b -> print_char (if b then '#' else ' ')) arr;
  print_newline ()

let () =
  let size = 21 in
  let gen = Array.make size false in
  gen.(size / 2) <- true;
  print_gen gen;
  let g1 = step gen in print_gen g1;
  let g2 = step g1  in print_gen g2;
  Printf.printf "Store comonad: cellular automaton\n"

Key Differences

Aspect	Rust	OCaml
Getter sharing	`Rc<dyn Fn(S) -> A>`	closure captured in record
Clone constraint	`S: Clone` required	structural copy for records
extend lifetime	`'static` bounds needed	no lifetime tracking
Lens connection	explicit derivation	directly via records
Performance	zero-cost with monomorphization	GC-managed closures

Store comonad is the semantic foundation of the van Laarhoven lens encoding. Lenses are exactly Store coalgebras: a -> Store b b with the right coherence laws.

OCaml Approach

In OCaml, Store is a record with a functional getter:

type ('s, 'a) store = { pos: 's; getter: 's -> 'a }

let extract { pos; getter } = getter pos
let seek s { getter; _ } = { pos = s; getter }
let peek s { getter; _ } = getter s

let extend f w =
  { pos = w.pos
  ; getter = fun s -> f { pos = s; getter = w.getter } }

let duplicate w =
  { pos = w.pos
  ; getter = fun s -> { pos = s; getter = w.getter } }

OCaml's polymorphic records make the types cleaner; Rust's Rc<dyn Fn> achieves the same but requires explicit sharing.

Full Source

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

(* Store comonad: models a mutable store.
   Store s a = (s -> a) * s
   extract: read current value
   extend: transform the getter, keeping the store *)

type ('s, 'a) store = Store of ('s -> 'a) * 's

let pos   (Store (_, s)) = s
let peek  (Store (f, _)) s = f s
let extract (Store (f, s)) = f s

let extend (Store (f, s)) g =
  Store ((fun s' -> g (Store (f, s'))), s)

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

(* A 1D cellular automaton via Store comonad! *)
(* The store is: int (position) -> bool (alive/dead), with current focus *)

let make_store arr pos =
  Store ((fun i ->
    let len = Array.length arr in
    let i' = ((i mod len) + len) mod len in
    arr.(i')
  ), pos)

let rule30 store =
  let left  = peek store (pos store - 1) in
  let cur   = extract store in
  let right = peek store (pos store + 1) in
  match (left, cur, right) with
  | (true,  true,  true)  -> false
  | (true,  true,  false) -> false
  | (true,  false, true)  -> false
  | (true,  false, false) -> true
  | (false, true,  true)  -> true
  | (false, true,  false) -> true
  | (false, false, true)  -> true
  | (false, false, false) -> false

let step arr =
  let len = Array.length arr in
  let store = make_store arr 0 in
  Array.init len (fun i ->
    let s = extend store (fun _ -> ()) in
    let s2 = Store ((fun i' ->
      let (Store (f, _)) = store in f i'), i) in
    rule30 s2
  )

let print_gen arr =
  Array.iter (fun b -> print_char (if b then '#' else ' ')) arr;
  print_newline ()

let () =
  let size = 21 in
  let gen = Array.make size false in
  gen.(size / 2) <- true;
  print_gen gen;
  let g1 = step gen in print_gen g1;
  let g2 = step g1  in print_gen g2;
  Printf.printf "Store comonad: cellular automaton\n"

Deep Comparison

OCaml vs Rust: Store 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 fmap for Store<S, A> — map over the result type without changing the position.

Verify the three comonad laws (left identity, right identity, associativity) with unit tests.

Build a 2D Store<(usize, usize), Cell> that represents a Game of Life grid and apply extend to compute one generation step.

Implement experiment: given a functor of positions F<S>, collect F<A> results by peeking at each position.

Show that Store s is equivalent to a coalgebra a -> s -> a paired with an s, connecting it to the lens definition.

Open Source Repos

functional-rust

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

Rust