236 Expert

Coyoneda

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Coyoneda" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. While the Yoneda lemma gives a free Functor for any type constructor from the "contravariant" side, Coyoneda gives a free Functor from the "covariant" side. Key difference from OCaml: 1. **GADT vs. Any**: OCaml's GADT existential keeps the type information in the pattern match; Rust's `Box<dyn Any>` erases it and requires downcasting.

Tutorial

The Problem

While the Yoneda lemma gives a free Functor for any type constructor from the "contravariant" side, Coyoneda gives a free Functor from the "covariant" side. Coyoneda<F, A> is an existential type that wraps a value F<B> and a function B -> A, deferring the fmap until it is needed. The practical use: you can make any type constructor a Functor for free using Coyoneda, even if it does not natively support map. This is the foundation of the free applicative and free monad.

🎯 Learning Outcomes

• Understand Coyoneda as an existential wrapper that provides free map for any type constructor

• Learn the construction: Coyoneda<F, A> = exists B. (F<B>, B -> A)

• See how Coyoneda accumulates map calls without evaluating the underlying functor

• Connect Coyoneda to free applicatives and free monads as building blocks

Code Example

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

(* Coyoneda: the free functor. Wraps a value and defers the mapping.
   Coyoneda f a = exists b. f b * (b -> a)
   Any type constructor becomes a functor for free via Coyoneda. *)

(* Existential Coyoneda *)
type 'f coyoneda_inj = {
  inject: 'b 'a. ('b -> 'a) -> 'b -> 'f
}

(* Using GADT to pack existential *)
type _ coyoneda =
  | Coyoneda : ('b -> 'a) * 'b list -> 'a coyoneda

(* Constructor *)
let lift lst = Coyoneda ((fun x -> x), lst)

(* fmap: compose the function, don't traverse yet *)
let fmap f (Coyoneda (g, lst)) = Coyoneda ((fun x -> f (g x)), lst)

(* Lower: apply the accumulated function *)
let lower (Coyoneda (f, lst)) = List.map f lst

let () =
  let colist = lift [1; 2; 3; 4; 5] in

  (* Fuse three maps — they compose, only one traversal at lower *)
  let result =
    colist
    |> fmap (fun x -> x * 2)
    |> fmap (fun x -> x + 1)
    |> fmap string_of_int
    |> lower
  in
  Printf.printf "Coyoneda fused: [%s]\n" (String.concat ";" result);

  (* No functor constraint needed — works for any type constructor *)
  Printf.printf "Coyoneda: deferred functor mapping\n"

Key Differences

GADT vs. Any: OCaml's GADT existential keeps the type information in the pattern match; Rust's Box<dyn Any> erases it and requires downcasting.

Free Functor: Coyoneda provides a free functor for any F regardless of whether F supports fmap; this is useful for uninspectable data sources.

Map fusion: Both accumulate map calls into a function composition — O(1) per map call; evaluation is deferred until run.

Free monad connection: Coyoneda is used as the base for free monads when the underlying functor does not have a natural fmap.

OCaml Approach

OCaml's Coyoneda uses GADT existentials:

type 'a 'f coyoneda = Coyoneda : 'b 'f * ('b -> 'a) -> 'a 'f coyoneda
let lift fb = Coyoneda (fb, Fun.id)
let map f (Coyoneda (fb, g)) = Coyoneda (fb, f >> g)
let run (Coyoneda (fb, f)) = map f fb  (* requires F to be a Functor *)

The GADT hides 'b — the existential type — while preserving the function 'b -> 'a. Map fusion is compositional: each map just extends the function.

Full Source

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

(* Coyoneda: the free functor. Wraps a value and defers the mapping.
   Coyoneda f a = exists b. f b * (b -> a)
   Any type constructor becomes a functor for free via Coyoneda. *)

(* Existential Coyoneda *)
type 'f coyoneda_inj = {
  inject: 'b 'a. ('b -> 'a) -> 'b -> 'f
}

(* Using GADT to pack existential *)
type _ coyoneda =
  | Coyoneda : ('b -> 'a) * 'b list -> 'a coyoneda

(* Constructor *)
let lift lst = Coyoneda ((fun x -> x), lst)

(* fmap: compose the function, don't traverse yet *)
let fmap f (Coyoneda (g, lst)) = Coyoneda ((fun x -> f (g x)), lst)

(* Lower: apply the accumulated function *)
let lower (Coyoneda (f, lst)) = List.map f lst

let () =
  let colist = lift [1; 2; 3; 4; 5] in

  (* Fuse three maps — they compose, only one traversal at lower *)
  let result =
    colist
    |> fmap (fun x -> x * 2)
    |> fmap (fun x -> x + 1)
    |> fmap string_of_int
    |> lower
  in
  Printf.printf "Coyoneda fused: [%s]\n" (String.concat ";" result);

  (* No functor constraint needed — works for any type constructor *)
  Printf.printf "Coyoneda: deferred functor mapping\n"

Deep Comparison

OCaml vs Rust: Coyoneda

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 map for Coyoneda<F, A> and verify that applying 5 maps results in a single composed function.

Write run: Coyoneda<Option, A> -> Option<A> that evaluates the deferred computation.

Demonstrate that Coyoneda provides a valid Functor instance: verify the identity and composition laws.

Open Source Repos

functional-rust

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

Rust