🔢 mathematics

Measuring data types

This paper unifies Sweedler's theory of measuring coalgebras with the categorical semantics of W-types to demonstrate that algebras of certain endofunctors are enriched in coalgebras of the same endofunctor, thereby generalizing the concept of initial algebras and providing new examples through polynomial endofunctors.

Original authors: Lukas Mulder, Paige Randall North, Maximilien Péroux

Published 2026-07-08

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lukas Mulder, Paige Randall North, Maximilien Péroux

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A New Way to Compare Computer Programs

Imagine you are a software engineer. You have two different computer programs (let's call them Program A and Program B). Usually, to see if they are related, you ask: "Can I turn Program A into Program B perfectly?" In math and computer science, this is called a homomorphism. It's like checking if two Lego structures are built exactly the same way, just with different colored bricks.

But what if they aren't perfect matches? What if Program A is a bit messy, or Program B is missing a few pieces? In the real world, we often deal with "almost right" or "partially correct" transformations.

This paper introduces a new mathematical tool called Measuring. Instead of just asking "Can I turn A into B perfectly?", it asks: "How close can I get, and how much of A can I successfully translate into B before I run into a wall?"

The authors combine two existing mathematical ideas to create this new tool:

Measuring Coalgebras: A classic idea from algebra about measuring how well two things fit together.
W-Types: The mathematical foundation for how computer languages (like Haskell or Agda) define data structures like lists, trees, and numbers.

The Core Concept: The "Partial Translator"

Think of a Homomorphism (a perfect translator) as a fluent speaker who can translate an entire book from English to French without making a single mistake.

The authors introduce the concept of a Partial Homomorphism (a partial translator). Imagine a translator who knows the first 10 pages of the book perfectly, but then gets stuck on page 11.

In traditional math, this translator is a "failure" because they didn't finish the whole book.
In this paper's new system, this translator is valuable! We can measure exactly how far they got.

The paper proves that for any two data structures (like a list of numbers or a tree of files), there isn't just a "Yes/No" answer on whether they match. Instead, there is a whole spectrum of "partial matches."

The "Tower of Approximations"

One of the coolest ideas in the paper is the Tower of Coalgebras.

Imagine you are trying to build a bridge between two cliffs (Program A and Program B).

Level 0: You can only connect the very first step.
Level 1: You can connect the first two steps.
Level 2: You can connect the first three steps.
...
Level Infinity: You have built the perfect, complete bridge.

The paper shows that you can build a mathematical "tower" where each level represents a slightly better, more complete connection between the two programs.

If you can only build a bridge up to Level 5, the math tells you exactly that.
If you can build it all the way to the top (Infinity), you have a perfect match.

This allows us to study "broken" or "incomplete" programs not as failures, but as valid, measurable steps toward a perfect solution.

The "Universal Measuring Device"

The authors also discovered a "Universal Measuring Device" (called the Universal Measuring Coalgebra).

Think of this as a Swiss Army Knife for comparisons.

If you have a specific data type (like a List of Integers), this device can tell you exactly how many different ways you can partially translate it into another type.
It doesn't just give you a list of perfect matches; it gives you a map of all the possible "almost matches," organized by how deep or complex they are.

Why This Matters (According to the Paper)

The paper doesn't claim this will immediately fix bugs in your code or cure diseases. Instead, it claims to:

Deepen our understanding of math: It shows that the "messy" world of partial connections is just as structured and beautiful as the "perfect" world of total connections.
Generalize "W-Types": In computer science, "W-Types" are the standard way to define recursive data (like lists and trees). This paper says, "We can generalize this." We can now define "C-Initial Algebras," which are like data types that are "initial" (the starting point) relative to a specific measuring device, rather than just being the absolute starting point.
Provide a framework for "Partial Induction": Usually, to prove something about a list, you use induction (prove it for the first item, then prove if it works for $n$ , it works for $n+1$ ). This paper suggests a way to do induction that stops partway through, allowing us to reason about processes that might not finish or might only work for a limited depth.

Summary Analogy

Imagine you are trying to fit a key (Program A) into a lock (Program B).

Old Math: The key either fits perfectly (it's a homomorphism), or it doesn't (it's not).
This Paper: The key might fit halfway in. Or it might fit in the first two teeth but jam on the third. The paper provides a ruler to measure exactly how far the key goes in. It builds a ladder of "fits" from "barely touches" to "perfectly turns."

By combining the math of "measuring" with the math of "data types," the authors have created a more precise, nuanced way to look at how computer programs interact, allowing us to appreciate the value of "almost right" just as much as "perfectly right."

Technical Summary: Measuring Data Types

Problem Statement
Functional programming languages (e.g., Haskell, Agda, Coq) rely heavily on inductive data types, which are categorically justified as initial algebras of endofunctors, specifically polynomial endofunctors known as W-types. While the categorical semantics of these types are well-understood as initial algebras, the paper identifies a gap in the mathematical structure surrounding them. Specifically, the standard categorical framework treats hom-sets between algebras as mere sets of total homomorphisms. This fails to capture "partial" or "approximate" structural relationships between data types, which are crucial for understanding how morphisms interact with inductive structures in a graded or layered manner. The authors seek to elucidate the structure in which W-types are embedded by drawing an analogy to Sweedler's classic theory of measuring coalgebras, where algebras over a field are enriched in coalgebras.

Methodology
The paper employs a synthesis of two distinct categorical theories:

Sweedler's Measuring Coalgebras: The authors review the classical theory where $k$ -algebras are enriched in $k$ -coalgebras. In this setting, the hom-object between two algebras is not a set of homomorphisms but a coalgebra of "partial homomorphisms" (or measurings). These measurings allow for morphisms that are "almost" homomorphisms, with the coalgebra structure encoding "how close" a morphism is to being a total homomorphism.
W-Types and Inductive Data Types: The paper reviews the categorical semantics of inductive types as initial algebras of endofunctors (specifically polynomial endofunctors).

The core methodology involves generalizing Sweedler's theory from the context of algebras over a field to algebras of an arbitrary endofunctor $F$ on a symmetric monoidal closed category $\mathcal{C}$ . The authors assume $\mathcal{C}$ is locally presentable and that $F$ is an accessible, lax symmetric monoidal endofunctor. They construct an enrichment of the category of $F$ -algebras ( $\text{Alg}_F$ ) over the category of $F$ -coalgebras ( $\text{coAlg}_F$ ).

Key technical steps include:

Defining measurings (maps $C \otimes A \to B$ ) and partial homomorphisms (maps $C \to [A, B]$ ) for $F$ -algebras and $F$ -coalgebras.
Proving the existence of a universal measuring coalgebra $\text{Alg}(A, B)$ , which serves as the hom-object in the enriched category.
Constructing the measuring tensor $C \triangleright A$ and the convolution algebra $[C, B]$ to establish that the category is tensored and cotensored.
Generalizing the notion of initial algebras to $C$ -initial algebras, where $C$ is a coalgebra, analogous to weighted limits in enriched category theory.

Key Contributions and Results

Enrichment of Algebras in Coalgebras (Theorem 10):
The central result states that for a locally presentable, closed symmetric monoidal category $\mathcal{C}$ and an accessible, lax symmetric monoidal endofunctor $F$ , the category of $F$ -algebras is enriched, tensored, and cotensored over the category of $F$ -coalgebras.
- Instead of a set of homomorphisms $\text{Alg}(A, B)$ , there exists a coalgebra $\text{Alg}(A, B)$ representing all possible partial homomorphisms.
- This enrichment is characterized by natural isomorphisms:
  $\text{coAlg}(C, \text{Alg}(A, B)) \cong \text{Alg}(C \triangleright A, B) \cong \text{Alg}(A, [C, B])$
Generalization of W-Types:
The authors generalize the concept of W-types (initial algebras of polynomial endofunctors) to $C$ -initial algebras. A $C$ -initial algebra is an algebra $A$ such that for any algebra $X$ , there is a unique coalgebra homomorphism $C \to \text{Alg}(A, X)$ . This allows for a more nuanced classification of inductive types based on the "shape" or "depth" encoded by the coalgebra $C$ .
Tower of Partial Homomorphisms:
The paper constructs a tower of coalgebras $\text{Alg}_n(A, B)$ representing $n$ -partial homomorphisms. The limit of this tower, $\text{Alg}_\infty(A, B)$ , corresponds to $\infty$ -partial homomorphisms, which approximate total algebra homomorphisms. This provides a formal mechanism for "partial induction," where one can inductively build homomorphisms layer by layer.
Explicit Examples and Calculations:
The theory is applied to several standard data types in computer science, including:
- Unit and Empty Types: Demonstrating trivial enrichments.
- Monoid Types: Showing how the monoidal structure introduces "twists" in measurings.
- Natural Numbers: Calculating the universal measuring coalgebra for preinitial algebras (finite truncations of $\mathbb{N}$ ) and proving that the finite truncation $n$ is the terminal $n^\circ$ -initial algebra.
- Lists and Trees: Extending the theory to list types (over a monoid) and binary/general trees. The authors demonstrate how measurings can control both the "shape" (depth/branching) and the "twist" (element-wise modification) of data structures. For instance, they show that while a total algebra homomorphism from a truncated list to the full list type may not exist, a measuring does.

Significance and Claims
The paper claims to provide a "purest form" of Sweedler's phenomenon by applying it to endofunctors, which lack the coherence constraints (units, multiplication) of traditional algebras. The authors argue that this enrichment offers higher-precision tools for studying interactions between algebras, moving beyond the binary distinction of "is a homomorphism" or "is not."

The significance is twofold:

Pure Mathematics: It unifies the theory of measuring coalgebras with the theory of W-types, extending the scope of Sweedler's theory to a broader categorical setting. It generalizes the notion of initial algebras to $C$ -initial algebras, offering a new perspective on inductive types.
Programming Language Theory: The framework provides a categorical justification for "partial" operations on inductive types. The authors suggest that this structure could eventually inform the implementation of inductive types in functional programming languages (like Haskell), potentially allowing for more flexible handling of partial data or infinite streams.

The paper explicitly notes that it is an extended version of a previous work [20], adding expository introductions, complete proofs, and a generalized tower construction for partial induction. It acknowledges that while the theory is established for specific endofunctors (like those for lists and trees), the functoriality of the construction in the category $\mathcal{C}$ and the endofunctor $F$ remains a topic for future work. Similarly, concrete implementations in programming languages are identified as a future direction rather than a current result.