Metaphorisms Deriving Divide and Conquer Recursive Programs
summary
Claims a recipeic path from Bird–Meertens formalism via metaphorisms to derive divide‑and‑conquer programs, shows the actual algebraic transformations used, and plugs them into recursion schemes. Implements compressed permutation structures and a succinct‑style compressed text approach in Scala, reimplements the dc‑3 (skew) suffix array algorithm functionally, and reports it runs (open source version limits forced a fresh implementation). Demonstrates merge sort emerging from the specification.
AI-written summary · about
chapters (29)
- 0:00Introduction
- 1:54Abstract
- 4:03Overview
- 5:00Visual Analytics
- 7:05Motivation
- 8:43What is succinct
- 12:26What is categorical calculus and relations
- 13:08What is squiggle
- 13:45Properties of your programs
- 14:02Book
- 14:48Sliding Tales Theorem
- 16:09Metaphorisms
- 17:04Metaphors in Software
- 17:27Metaphors We Live By
- 18:21Formal Metaphors
- 20:52Concrete Metaphors
- 22:40Function converses
- 24:34Text formatting
- 27:42endo relation better
- 32:05canonical methods
- 34:35sorting example
- 37:41sorting algorithm
- 38:59transforming spec into functional program
- 39:29relational spec
- 40:33y function
- 41:01Mystery sort
- 44:54Conclusion
- 45:52Research Team
- 46:08Questions
related talks
01h 37mThe Art of Program Derivation and Parallel Computation
23mFree the Conqueror! (Refactoring divide-and-conquer functions)
01h 35mRecursion Schemes, Algebras, Finally Tagless, Data Types
25mFrom `goto` Statements to Recursion Schemes
59mThe Power of Function Composition
28mMetaphors We Compute By
59mBuilding an Intuition for Composition
41mThe Free Monad by Example