Monads & Comonads

Monads

A monad \(T: \mathcal{C} \to \mathcal{C}\) is an endofunctor with two natural transformations:

satisfying associativity and unitality (monad laws):

\[ \mu \circ \mu T = \mu \circ T \mu, \quad \mu \circ \eta T = \text{id}, \quad \mu \circ T \eta = \text{id} \]

The Monad abstract class defines this interface:

from quivers.monadic.monads import Monad
from quivers.core.objects import FinSet

class MyMonad(Monad):
    def unit(self, obj):
        """η: obj → T(obj)"""
        raise NotImplementedError()

    def multiply(self, obj):
        """μ: T(T(obj)) → T(obj)"""
        raise NotImplementedError()

    def map(self, f):
        """Functor action: f → T(f)"""
        raise NotImplementedError()

Kleisli Category

Every monad \(T\) induces a Kleisli category \(\mathcal{C}_T\) where: - Objects are the same as \(\mathcal{C}\) - Morphisms \(X \rightsquigarrow Y\) are morphisms \(X \to T(Y)\) in \(\mathcal{C}\) - Composition is Kleisli composition: \((g \circ_T f)(x) = \mu(T(g)(f(x)))\)

In quivers:

from quivers.monadic.monads import KleisliCategory

kleisli = KleisliCategory(monad=my_monad)

# Kleisli morphisms: f: A ⇝ B is really A → T(B)
f = kleisli.morphism_from_data(X, Y, tensor_data)

# Kleisli composition
g = kleisli.morphism_from_data(Y, Z, tensor_data)
h = kleisli.compose(f, g)  # properly flattens via μ

Fuzzy Powerset Monad

The fuzzy powerset monad on the category of finite sets with the product fuzzy quantale:

from quivers.monadic.monads import FuzzyPowersetMonad
from quivers.core.objects import FinSet
from quivers.core.quantales import PRODUCT_FUZZY

X = FinSet("X", 3)

monad = FuzzyPowersetMonad()

# T(X) = X (objects unchanged)
TX = monad.unit(X)
assert TX == X

# But the enrichment becomes fuzzy (PRODUCT_FUZZY)
# A morphism A → B in the Kleisli category is really A → T(B) = A → B
# with composition via noisy-OR (join in PRODUCT_FUZZY)

The Kleisli category of the fuzzy powerset monad is equivalent to the category of fuzzy relations, where composition uses the noisy-OR join.

Free Monoid Monad

The free monoid monad on the category of finite sets:

from quivers.monadic.monads import FreeMonoidMonad
from quivers.core.objects import FinSet, FreeMonoid

monad = FreeMonoidMonad(max_length=3)

X = FinSet("X", 5)

# T(X) = Free Monoid on X, truncated to max_length
TX = monad.map(X)
assert isinstance(TX, FreeMonoid)
assert TX.generators == X
assert TX.max_length == 3

Comonads

A comonad \(W: \mathcal{C} \to \mathcal{C}\) is a dual monad with:

from quivers.monadic.comonads import Comonad

class MyComonad(Comonad):
    def extract(self, obj):
        """ε: W(obj) → obj"""
        raise NotImplementedError()

    def duplicate(self, obj):
        """δ: W(obj) → W(W(obj))"""
        raise NotImplementedError()

    def comap(self, f):
        """Functor action: f → W(f)"""
        raise NotImplementedError()

CoKleisli Category

The coKleisli category \(\mathcal{C}^W\) has: - Objects as in \(\mathcal{C}\) - Morphisms \(X \rightleftharpoons Y\) are morphisms \(W(X) \to Y\) in \(\mathcal{C}\) - Composition: \((g \circ^W f) = \text{extend}(g, f)\)

from quivers.monadic.comonads import CoKleisliCategory

cokleisli = CoKleisliCategory(comonad=my_comonad)

f = cokleisli.morphism_from_data(X, Y, tensor_data)
g = cokleisli.morphism_from_data(Y, Z, tensor_data)
h = cokleisli.compose(f, g)

Diagonal Comonad

The diagonal (or duplication) comonad duplicates its input:

from quivers.monadic.comonads import DiagonalComonad

X = FinSet("X", 3)

comonad = DiagonalComonad()

# W(X) = X × X (duplication)
WX = comonad.map(X)
assert WX == X * X

# extract projects back to X (first or second component)
# duplicate sends X × X to (X × X) × (X × X)

Cofree Comonad

The cofree comonad generated by an endofunctor \(F\):

from quivers.monadic.comonads import CofreeComonad

# Cofree monad of functor F
cofree = CofreeComonad(functor=F)

# W(X) = X + F(X) + F²(X) + ...

Algebras and Coalgebras

An algebra for a monad \(T\) is a morphism \(a: T(X) \to X\) satisfying:

\[ a \circ \eta_X = \text{id}_X, \quad a \circ \mu_X = a \circ T(a) \]

A coalgebra for a comonad \(W\) is a morphism \(c: X \to W(X)\) satisfying the dual laws.

from quivers.monadic.algebras import Algebra, Coalgebra

# T-algebra: action that respects monad structure
algebra = Algebra(monad=T, carrier=X, action=a)

# W-coalgebra: structure that respects comonad
coalgebra = Coalgebra(comonad=W, carrier=X, structure=c)

# Algebra homomorphism: f: (X, a) → (Y, b) such that b ∘ T(f) = f ∘ a
hom = algebra.homomorphism_to(other_algebra)

Eilenberg-Moore Category

The Eilenberg-Moore category \(\mathcal{C}^T\) of a monad \(T\) has: - Objects: \(T\)-algebras \((X, a: T(X) \to X)\) - Morphisms: algebra homomorphisms

The forgetful functor \(U: \mathcal{C}^T \to \mathcal{C}\) forgets the algebra structure, and the free functor \(F: \mathcal{C} \to \mathcal{C}^T\) sends \(X\) to \((T(X), \mu_X)\) (the monad itself is an algebra).

from quivers.monadic.algebras import EilenbergMooreCategory

em = EilenbergMooreCategory(monad=T)

# Free algebra on X
free_alg = em.free(X)
assert free_alg.carrier == T.map(X)
assert free_alg.action == T.multiply(X)

# Algebra from explicit action
explicit_alg = em.algebra(X, a)

# Homomorphism between algebras
hom = em.homomorphism(alg1, alg2)

Distributive Laws

A distributive law \(\lambda: T \circ S \Rightarrow S \circ T\) between endofunctors \(T\) and \(S\) allows lifting one monad through another.

from quivers.monadic.distributive_laws import DistributiveLaw

# Distributive law: T ∘ S ⇒ S ∘ T
dlaws = DistributiveLaw(T, S, components)

# Lift monad T through monad S
lifted_T = dlaws.lift(T)

The FreeMonoidPowersetLaw distributes the free monoid monad over the fuzzy powerset monad:

from quivers.monadic.distributive_laws import FreeMonoidPowersetLaw

law = FreeMonoidPowersetLaw(monad_T=free_monoid, monad_S=fuzzy_powerset)

# Use to compose programs that involve both monads