🔢 mathematics

On Graded Monads, Distributive Laws and Costrong Functors

This paper introduces the concept of costrong functors as a dual to strong functors, demonstrating that their costrength corresponds to graded distributive laws and generalizing the relationship between endofunctors and monads to the graded setting with applications in optics and coalgebras.

Original authors: Adriana Balan (Department of Mathematical Methods,Models,,Fundamental Sciences Applied in Engineering Research Center, National University of Science,Technology POLITEHNICA Bucharest), Silviu-George P

Published 2026-07-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Adriana Balan (Department of Mathematical Methods,Models,,Fundamental Sciences Applied in Engineering Research Center, National University of Science,Technology POLITEHNICA Bucharest), Silviu-George Pantelimon (Department of Computer Science, National University of Science,Technology POLITEHNICA Bucharest)

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 Invisible Backpack and the Magic Suction Cup

Imagine you are trying to understand how computers think. In the world of software, we often talk about "effects"—things like making a mistake, waiting for a file, or remembering a password. These aren't just bugs; they are features that change how a program behaves. For decades, computer scientists have used a clever mathematical tool called a "monad" to organize these effects. Think of a monad as a special kind of backpack. When you put a piece of data (like a number) into this backpack, the backpack doesn't just hold it; it carries the baggage of the entire journey, like a log of every step taken or a record of every error made.

But there's another side to this story. Sometimes, instead of stuffing data into a backpack, we need to pull information out of a complex machine to see what's happening inside. Imagine a black box that processes your data. Usually, we can only see the final result. But what if the machine had a secret door, a "suction cup," that let us peek inside, grab a piece of the internal state, and look at it without breaking the machine? This is the idea of "costrength." While the "strength" of a monad pushes data in, "costrength" pulls data out. It's a concept that has been hiding in plain sight, mostly ignored because it's harder to find in the messy world of real-world programming. This paper is about finally giving that hidden suction cup the attention it deserves, showing how it connects to a newer, more flexible way of grading these backpacks, and proving that it's the key to understanding how data flows in and out of complex systems.

The Paper's Big Idea: Graded Backpacks and the Art of Pulling Data Out

This paper, written by Adriana Balan and Silviu-George Pantelimon, dives deep into the mathematics of how functors (which are like data containers or machines) interact with these "graded monads" (the fancy backpacks). The authors argue that while everyone has been studying how to push data into these containers (a property called "strength"), they have largely missed the dual property: how to pull data out (called "costrength").

The core discovery is that "costrength" isn't just a weird, opposite version of strength; it's actually a specific type of "graded distributive law." To understand this, imagine you have a machine that processes a stream of letters. A "distributive law" is a rule that lets you swap the order of operations: you can either process the letters first and then pack them into a box, or pack them first and then process the box. The authors show that when you have a "graded" system (where the backpack has a label indicating how it was filled, like "error log" or "success log"), the ability to pull data out of the machine (costrength) is mathematically identical to having a rule that lets you swap the order of the machine and the backpack.

The paper proves that this isn't just a theoretical curiosity. The authors demonstrate that if you have a "costrong" functor, you can lift it into a "Kleisli category." In plain English, this means you can take a complex system (like a stream of data) and wrap it in a context (like a logging system) without losing the ability to see the original stream. They show that this works perfectly for "graded" systems, where the context might change depending on the situation.

One of the most concrete findings is about "cartesian categories," which are basically the standard world of sets and functions we use in everyday programming. The authors prove a surprising equivalence here: in this specific world, having a "costrength" is exactly the same thing as having a "copoint." A copoint is a simple rule that lets you extract a value from a container. For example, if you have a container of "logs," a copoint lets you grab the log itself. The paper shows that in this standard world, costrength isn't a mysterious, extra layer of magic; it's just the ability to look inside the box. This explains why it was overlooked: in standard programming, it's so common to be able to look inside a box that nobody gave it a special name. However, the authors argue that in more complex, non-standard mathematical worlds (which are becoming more common in advanced computing), this "suction cup" property becomes a vital, distinct structure.

The paper also explores how this applies to "optics," which are tools used to access and modify parts of complex data structures (like zooming in on a specific field in a database). The authors show that you can transform these optics using a pair of functors: one that pushes data in (strong) and one that pulls data out (costrong). This allows you to change the context of your data access without breaking the connection between the two sides.

Furthermore, the authors apply this to "streams" of data, like a continuous flow of sensor readings. They show that if your data processor is "costrong," you can wrap the entire stream in a context (like a simulation or a filter) and still be able to see the output stream clearly. This leads to a powerful principle called "coinduction up-to," which allows programmers to prove that two complex systems behave the same way, even if they are wrapped in different layers of context.

The authors are careful to note that while they have established a solid mathematical framework for this, there is still much to explore. They explicitly state that they focused on the "Kleisli" version of these laws (which deals with how to sequence actions) and did not fully explore the "Eilenberg-Moore" version (which deals with algebraic models), though they suggest that the latter is also an interesting area for future work. They also clarify that while costrength is a powerful tool, it doesn't exist for every single type of functor; for instance, in standard set theory, a functor that creates a "Maybe" (a value that might be missing) cannot be costrong in the standard way because you can't always pull a value out of a "nothing."

In short, the paper doesn't claim to have solved every problem in computer science. Instead, it shines a light on a neglected corner of the mathematical landscape. It suggests that by understanding "costrength" as a "graded distributive law," we can build better, more modular ways to handle data that changes, logs events, or flows in streams. It turns a hidden feature of mathematics into a visible tool for building more robust software.

Technical Summary: On Graded Monads, Distributive Laws and Costrong Functors

Problem Statement

The paper addresses a structural asymmetry in category theory and computer science regarding "strong" and "costrong" functors. While strong functors (equipped with a natural transformation $st_{M,X}: M \otimes FX \to F(M \otimes X)$ ) are ubiquitous in modeling computational effects and are well-understood in the context of enriched categories and functional programming, their dual concept, costrong functors (equipped with $cst_{M,X}: F(M \otimes X) \to M \otimes FX$ ), has remained largely unobserved and under-theorized.

The authors argue that this neglect is partly due to the specific properties of the cartesian category of sets ( $\mathbf{Set}$ ), where every endofunctor admits a unique strength, and costrong functors coincide trivially with copointed functors (those with a natural transformation $FX \to X$ ). However, in more general monoidal categories and graded settings, "being costrong" represents a non-trivial structure that governs how functors interact with monoidal actions. The paper seeks to formalize this duality, establish its relationship with graded monads and graded distributive laws, and demonstrate its utility in contexts such as optics and coalgebraic stream semantics.

Methodology

The paper employs a dual perspective, bridging two established frameworks:

Graded Monads and Distributive Laws: The authors generalize the classical correspondence between distributive laws ( $FT \to TF$ ) and liftings to the Kleisli category from ordinary monads to $M$ -graded monads. They define a graded distributive law as a family of natural transformations $\lambda_M: FTM \to TMF$ compatible with the graded monad's unit and multiplication.
Actegories and Costrong Functors: They reinterpret graded monads (specifically those where the unit and multiplication are isomorphisms) as actions of a monoidal category (actegories). Within this framework, functors equipped with a graded distributive law are identified as costrong functors (morphisms of actegories).

The methodology proceeds by:

Defining the Kleisli category for graded monads using coends to handle the grading structure.
Proving a one-to-one correspondence between graded distributive laws of an endofunctor over a graded monad and liftings of that functor to the graded Kleisli category.
Analyzing the specific case of cartesian categories, where the authors prove an isomorphism between the category of costrong endofunctors and the category of copointed endofunctors.
Investigating categorical properties of costrong functors, including their compositionality, behavior under colimits, and relationship to adjunctions and profunctors.

Key Contributions and Results

1. Generalization of Distributive Laws to Graded Settings

The paper establishes that the correspondence between distributive laws and Kleisli liftings extends to graded monads. A graded distributive law $\lambda_M: FTM \to TMF$ allows an endofunctor $F$ to be lifted to the Kleisli category of a graded monad $T$ . This generalization is crucial for understanding how effects (grades) interact with datatypes in a structured manner.

2. Identification of Costrength as a Graded Distributive Law

The central theoretical insight is the recognition that the costrength of a costrong functor is precisely a "graded" distributive law. Specifically, if a monoidal category $M$ acts on a category $A$ , a functor $F$ is costrong with respect to this action if and only if it distributes over the induced graded monad (the action itself). This unifies the concepts of costrength and graded distributive laws.

3. The Cartesian Case: Costrong $\cong$ Copointed

A significant result (Theorem 4.12) demonstrates that on a cartesian category (like $\mathbf{Set}$ ), the category of costrong endofunctors is isomorphic to the category of copointed endofunctors (functors $F$ equipped with $\epsilon: F \to \text{id}$ ).

Implication: In the cartesian setting, costrength carries no more information than the ability to extract a value from a computation (observation). The costrength is reconstructed from the copoint and the canonical projections of the product.
Examples: This explains why the Writer comonad ( $S \times -$ ) has a unique costrength (the second projection) and why the Reader monad's costrengths correspond to elements of the environment $S$ . Conversely, functors without copoints (e.g., those with constants like Maybe or List with no copoint) cannot be costrong in the cartesian setting.

4. Categorical Properties

The paper establishes several structural properties of costrong functors:

Compositionality: Costrong functors and costrong natural transformations form a 2-category ( $M\text{-Actcst}$ ), ensuring that the composition of costrong functors is costrong.
Colimits: The forgetful functor from costrong functors to ordinary functors creates colimits. Thus, coproducts of costrong functors are costrong.
Free Monads: Unlike strong functors (where strength does not necessarily pass to free monads), free monads inherit costrength from their generating functors (Proposition 4.23).
Profunctors: There is a duality where a functor $F$ is costrong if and only if its right adjoint profunctor $F^*$ is a strong profunctor (Tambara module).

5. Applications

The paper illustrates the utility of this framework in two specific domains:

Optics: The authors show that mixed optics (bidirectional data accessors) can be transformed by pairs of functors where one is strong and the other is costrong. This preserves the bidirectional behavior while varying the computational context, providing a conceptual justification for studying costrength.
Stream Coalgebras: For a costrong functor $F$ on $\mathbf{Set}$ , the costrength induces a distributive law over the Writer monad $M \times -$ . This allows $F$ to lift stream coalgebras (systems producing outputs in $M$ ) while preserving the observable output stream. This leads to a coinduction up-to principle, enabling modular reasoning about behavioral equivalence in systems wrapped by $F$ .

Significance and Claims

The paper claims that "being costrong" is not merely a dual curiosity but a fundamental structure that organizes how effects interact with datatypes, particularly in graded and coalgebraic contexts.

Theoretical Unification: It reveals that costrength is the graded analogue of distributive laws, organizing into a coherent 2-categorical structure that the ungraded theory obscures.
Practical Relevance: The framework provides a uniform way to reason about effects that expose internal state or allow observation (e.g., loggers, profilers, read-only environments), which are modeled as costrong endofunctors.
Foundational Shift: By dualizing the theory of strong functors, the paper argues that costrength is essential for understanding context-dependent computation and coalgebraic trace semantics, especially as monoidal structures beyond the cartesian product become more prevalent in programming language semantics.

The authors note that while the Kleisli construction for graded monads is inherently bicategorical, their direct approach using coends and distributive laws provides a practical handle on these structures. They acknowledge that the study of graded Eilenberg-Moore distributive laws remains an open direction for future work.