237 Expert

Day Convolution

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Day Convolution" functional Rust example. Difficulty level: Expert. Key concepts covered: Functional Programming. Day convolution is a monoidal product for functors: given two applicative functors `F` and `G`, `Day<F, G>` is their "tensor product." The construction packages values from both functors with a combining function, enabling them to be applied together. Key difference from OCaml: 1. **Monoidal structure**: Day convolution gives functors a tensor product; the unit of the monoid is the `Identity` functor — this is the categorical structure.

Tutorial

The Problem

Day convolution is a monoidal product for functors: given two applicative functors F and G, Day<F, G> is their "tensor product." The construction packages values from both functors with a combining function, enabling them to be applied together. Day convolution arises in effect systems (combining independent effect types), parser combinators (running two parsers on the same input), and signal processing abstractions. It is the categorical generalization of zip for applicatives.

🎯 Learning Outcomes

• Understand Day convolution as the monoidal product for functors/applicatives

• Learn the structure: Day<F, G, A> = exists B, C. (F<B>, G<C>, B -> C -> A)

• See how Day convolution relates to zip and parallel applicative composition

• Connect to the applicative functor laws through Day's monoidal structure

Code Example

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

(* Day convolution: a way to combine two functors.
   Day f g a = exists b c. f b * g c * (b -> c -> a)
   Used to build applicative functors compositionally. *)

(* Simplified Day convolution for lists *)
(* Day List List a = all ways to combine elements *)
type ('f, 'g, 'a) day =
  | Day : 'f * 'g * ('b -> 'c -> 'a) -> ('f, 'g, 'a) day

(* Day convolution of two lists = cartesian product *)
let day_product xs ys f =
  List.concat_map (fun x ->
    List.map (fun y -> f x y) ys
  ) xs

(* This IS the applicative for lists *)
let apply_list fs xs = day_product fs xs (fun f x -> f x)

let () =
  let xs = [1; 2; 3] in
  let ys = [10; 20] in

  (* Day convolution: all sums *)
  let sums = day_product xs ys ( + ) in
  Printf.printf "all sums: [%s]\n" (sums |> List.map string_of_int |> String.concat ";");

  (* All products *)
  let prods = day_product xs ys ( * ) in
  Printf.printf "all products: [%s]\n" (prods |> List.map string_of_int |> String.concat ";");

  (* Applicative from Day *)
  let fs = [(fun x -> x * 2); (fun x -> x + 1)] in
  let results = apply_list fs [1; 2; 3] in
  Printf.printf "apply: [%s]\n" (results |> List.map string_of_int |> String.concat ";")

Key Differences

Monoidal structure: Day convolution gives functors a tensor product; the unit of the monoid is the Identity functor — this is the categorical structure.

Two existentials: Day requires two existential types (B and C); Coyoneda requires one — Day is more complex.

Applications: Day convolution is used in adjunctions, comonad-transformers, and lens internals; it is primarily a theoretical/library tool.

Practical analogy: zip for lists and liftA2 for applicatives are the everyday incarnations of Day convolution in programming.

OCaml Approach

OCaml's Day convolution using GADTs:

type ('f, 'g, 'a) day =
  Day : 'b 'f * 'c 'g * ('b -> 'c -> 'a) -> ('f, 'g, 'a) day
let run_option (Day (fb, gc, f)) =
  match (fb, gc) with
  | (Some b, Some c) -> Some (f b c)
  | _ -> None

OCaml's GADT hides 'b and 'c cleanly. The run_option interpreter specializes Day to the Option functor.

Full Source

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

(* Day convolution: a way to combine two functors.
   Day f g a = exists b c. f b * g c * (b -> c -> a)
   Used to build applicative functors compositionally. *)

(* Simplified Day convolution for lists *)
(* Day List List a = all ways to combine elements *)
type ('f, 'g, 'a) day =
  | Day : 'f * 'g * ('b -> 'c -> 'a) -> ('f, 'g, 'a) day

(* Day convolution of two lists = cartesian product *)
let day_product xs ys f =
  List.concat_map (fun x ->
    List.map (fun y -> f x y) ys
  ) xs

(* This IS the applicative for lists *)
let apply_list fs xs = day_product fs xs (fun f x -> f x)

let () =
  let xs = [1; 2; 3] in
  let ys = [10; 20] in

  (* Day convolution: all sums *)
  let sums = day_product xs ys ( + ) in
  Printf.printf "all sums: [%s]\n" (sums |> List.map string_of_int |> String.concat ";");

  (* All products *)
  let prods = day_product xs ys ( * ) in
  Printf.printf "all products: [%s]\n" (prods |> List.map string_of_int |> String.concat ";");

  (* Applicative from Day *)
  let fs = [(fun x -> x * 2); (fun x -> x + 1)] in
  let results = apply_list fs [1; 2; 3] in
  Printf.printf "apply: [%s]\n" (results |> List.map string_of_int |> String.concat ";")

Deep Comparison

OCaml vs Rust: Day Convolution

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 run_vec: Day<Vec, Vec, A> -> Vec<A> using zip semantics.

Show that day(identity, fa, |(), a| a) is isomorphic to fa — the identity is the unit for Day.

Implement the applicative ap: Day<F, F, A> -> F<A> for Option<_>.

Open Source Repos

functional-rust

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

Rust