Algebras and Coalgebras¶

Monad algebras, comonad coalgebras, and their structural properties.

algebras ¶

Algebras and coalgebras for monads and comonads.

An algebra (A, α) for a monad (T, η, μ) consists of an object A and a morphism α: T(A) → A satisfying:

α ∘ η_A = id_A           (unit law)
α ∘ μ_A = α ∘ T(α)       (associativity)

Dually, a coalgebra (A, γ) for a comonad (W, ε, δ) consists of an object A and a morphism γ: A → W(A) satisfying:

ε_A ∘ γ = id_A           (counit law)
δ_A ∘ γ = W(γ) ∘ γ       (coassociativity)

The Eilenberg-Moore category of a monad T has T-algebras as objects and algebra homomorphisms as morphisms. The comparison functor K: Kl(T) → EM(T) relates the Kleisli and Eilenberg-Moore categories.

This module provides:

Algebra (abstract)
├── FreeAlgebra            — free T-algebra μ_A: T(T(A)) → T(A)
└── ObservedAlgebra        — algebra from a concrete structure map

Coalgebra (abstract)
├── CofreeCoalgebra        — cofree W-coalgebra δ_A: W(A) → W(W(A))
└── ObservedCoalgebra      — coalgebra from a concrete structure map

EilenbergMooreCategory     — the category of algebras for a monad

Algebra ¶

Algebra(monad: Monad, carrier: SetObject)

Bases: ABC

Abstract algebra for a monad.

An algebra (A, α) for monad T consists of a carrier object A and a structure map α: T(A) → A.

PARAMETER	DESCRIPTION
`monad`	The monad T. TYPE: `Monad`
`carrier`	The carrier object A. TYPE: `SetObject`

Source code in src/quivers/monadic/algebras.py

def __init__(self, monad: Monad, carrier: SetObject) -> None:
    self._monad = monad
    self._carrier = carrier

monad `property` ¶

monad: Monad

The monad T.

carrier `property` ¶

carrier: SetObject

The carrier object A.

structure_map `abstractmethod` ¶

structure_map() -> Morphism

The structure map α: T(A) → A.

RETURNS	DESCRIPTION
`Morphism`	The algebra structure map.

Source code in src/quivers/monadic/algebras.py

@abstractmethod
def structure_map(self) -> Morphism:
    """The structure map α: T(A) → A.

    Returns
    -------
    Morphism
        The algebra structure map.
    """
    ...

verify_unit_law ¶

verify_unit_law(atol: float = 1e-05) -> bool

Verify α ∘ η_A = id_A.

PARAMETER	DESCRIPTION
`atol`	Absolute tolerance for comparison. TYPE: `float` DEFAULT: `1e-05`

RETURNS	DESCRIPTION
`bool`	True if the unit law holds within tolerance.

Source code in src/quivers/monadic/algebras.py

def verify_unit_law(self, atol: float = 1e-5) -> bool:
    """Verify α ∘ η_A = id_A.

    Parameters
    ----------
    atol : float
        Absolute tolerance for comparison.

    Returns
    -------
    bool
        True if the unit law holds within tolerance.
    """
    alpha = self.structure_map()
    eta = self._monad.unit(self._carrier)
    result = (eta >> alpha).tensor
    expected = identity(self._carrier).tensor

    return torch.allclose(result, expected, atol=atol)

verify_associativity ¶

verify_associativity(atol: float = 1e-05) -> bool

Verify α ∘ μ_A = α ∘ T(α).

PARAMETER	DESCRIPTION
`atol`	Absolute tolerance for comparison. TYPE: `float` DEFAULT: `1e-05`

RETURNS	DESCRIPTION
`bool`	True if associativity holds within tolerance.

Source code in src/quivers/monadic/algebras.py

def verify_associativity(self, atol: float = 1e-5) -> bool:
    """Verify α ∘ μ_A = α ∘ T(α).

    Parameters
    ----------
    atol : float
        Absolute tolerance for comparison.

    Returns
    -------
    bool
        True if associativity holds within tolerance.
    """
    alpha = self.structure_map()
    mu = self._monad.multiply(self._carrier)

    # left side: α ∘ μ_A
    left = (mu >> alpha).tensor

    # right side: α ∘ T(α)
    t_alpha = self._monad.endofunctor.map_morphism(alpha)
    right = (t_alpha >> alpha).tensor

    return torch.allclose(left, right, atol=atol)

FreeAlgebra ¶

FreeAlgebra(monad: Monad, obj: SetObject)

Bases: Algebra

The free T-algebra on an object A.

The carrier is T(A) and the structure map is μ_A: T(T(A)) → T(A). This is the algebra that the comparison functor assigns to each object in the Kleisli category.

PARAMETER	DESCRIPTION
`monad`	The monad T. TYPE: `Monad`
`obj`	The base object A (the carrier will be T(A)). TYPE: `SetObject`

Source code in src/quivers/monadic/algebras.py

def __init__(self, monad: Monad, obj: SetObject) -> None:
    carrier = monad.endofunctor.map_object(obj)
    super().__init__(monad, carrier)
    self._base = obj

base `property` ¶

base: SetObject

The base object A (carrier is T(A)).

structure_map ¶

structure_map() -> Morphism

μ_A: T(T(A)) → T(A).

Source code in src/quivers/monadic/algebras.py

def structure_map(self) -> Morphism:
    """μ_A: T(T(A)) → T(A)."""
    return self._monad.multiply(self._base)

ObservedAlgebra ¶

ObservedAlgebra(monad: Monad, carrier: SetObject, structure_tensor: Tensor, algebra: Algebra | None = None)

Bases: Algebra

An algebra defined by an explicit structure map tensor.

PARAMETER	DESCRIPTION
`monad`	The monad T. TYPE: `Monad`
`carrier`	The carrier object A. TYPE: `SetObject`
`structure_tensor`	The tensor for α: T(A) → A. TYPE: `Tensor`
`algebra`	The enrichment algebra. Defaults to PRODUCT_FUZZY. TYPE: `Algebra or None` DEFAULT: `None`

Source code in src/quivers/monadic/algebras.py

def __init__(
    self,
    monad: Monad,
    carrier: SetObject,
    structure_tensor: torch.Tensor,
    algebra: VAlgebra | None = None,
) -> None:
    super().__init__(monad, carrier)
    q = algebra if algebra is not None else PRODUCT_FUZZY
    ta = monad.endofunctor.map_object(carrier)
    self._morphism = observed(ta, carrier, structure_tensor, algebra=q)

structure_map ¶

structure_map() -> Morphism

The stored structure map α: T(A) → A.

Source code in src/quivers/monadic/algebras.py

def structure_map(self) -> Morphism:
    """The stored structure map α: T(A) → A."""
    return self._morphism

Coalgebra ¶

Coalgebra(comonad: object, carrier: SetObject)

Bases: ABC

Abstract coalgebra for a comonad.

A coalgebra (A, γ) for comonad W consists of a carrier object A and a structure map γ: A → W(A).

PARAMETER	DESCRIPTION
`comonad`	The comonad W (a Comonad instance). TYPE: `object`
`carrier`	The carrier object A. TYPE: `SetObject`

Source code in src/quivers/monadic/algebras.py

def __init__(self, comonad: object, carrier: SetObject) -> None:
    self._comonad = comonad
    self._carrier = carrier

comonad `property` ¶

comonad: object

The comonad W.

carrier `property` ¶

carrier: SetObject

The carrier object A.

structure_map `abstractmethod` ¶

structure_map() -> Morphism

The structure map γ: A → W(A).

RETURNS	DESCRIPTION
`Morphism`	The coalgebra structure map.

Source code in src/quivers/monadic/algebras.py

@abstractmethod
def structure_map(self) -> Morphism:
    """The structure map γ: A → W(A).

    Returns
    -------
    Morphism
        The coalgebra structure map.
    """
    ...

verify_counit_law ¶

verify_counit_law(atol: float = 1e-05) -> bool

Verify ε_A ∘ γ = id_A.

PARAMETER	DESCRIPTION
`atol`	Absolute tolerance for comparison. TYPE: `float` DEFAULT: `1e-05`

RETURNS	DESCRIPTION
`bool`	True if the counit law holds within tolerance.

Source code in src/quivers/monadic/algebras.py

def verify_counit_law(self, atol: float = 1e-5) -> bool:
    """Verify ε_A ∘ γ = id_A.

    Parameters
    ----------
    atol : float
        Absolute tolerance for comparison.

    Returns
    -------
    bool
        True if the counit law holds within tolerance.
    """

    gamma = self.structure_map()
    eps = self._comonad.counit(self._carrier)  # type: ignore[union-attr]
    result = (gamma >> eps).tensor
    expected = identity(self._carrier).tensor

    return torch.allclose(result, expected, atol=atol)

verify_coassociativity ¶

verify_coassociativity(atol: float = 1e-05) -> bool

Verify δ_A ∘ γ = W(γ) ∘ γ.

PARAMETER	DESCRIPTION
`atol`	Absolute tolerance for comparison. TYPE: `float` DEFAULT: `1e-05`

RETURNS	DESCRIPTION
`bool`	True if coassociativity holds within tolerance.

Source code in src/quivers/monadic/algebras.py

def verify_coassociativity(self, atol: float = 1e-5) -> bool:
    """Verify δ_A ∘ γ = W(γ) ∘ γ.

    Parameters
    ----------
    atol : float
        Absolute tolerance for comparison.

    Returns
    -------
    bool
        True if coassociativity holds within tolerance.
    """

    gamma = self.structure_map()
    delta = self._comonad.comultiply(self._carrier)  # type: ignore[union-attr]

    # left side: δ_A ∘ γ
    left = (gamma >> delta).tensor

    # right side: W(γ) ∘ γ
    w_gamma = self._comonad.endofunctor.map_morphism(gamma)  # type: ignore[union-attr]
    right = (gamma >> w_gamma).tensor

    return torch.allclose(left, right, atol=atol)

CofreeCoalgebra ¶

CofreeCoalgebra(comonad: object, obj: SetObject)

Bases: Coalgebra

The cofree W-coalgebra on an object A.

The carrier is W(A) and the structure map is δ_A: W(A) → W(W(A)).

PARAMETER	DESCRIPTION
`comonad`	The comonad W. TYPE: `object`
`obj`	The base object A (the carrier will be W(A)). TYPE: `SetObject`

Source code in src/quivers/monadic/algebras.py

def __init__(self, comonad: object, obj: SetObject) -> None:
    carrier = comonad.endofunctor.map_object(obj)  # type: ignore[union-attr]
    super().__init__(comonad, carrier)
    self._base = obj

base `property` ¶

base: SetObject

The base object A (carrier is W(A)).

structure_map ¶

structure_map() -> Morphism

δ_A: W(A) → W(W(A)).

Source code in src/quivers/monadic/algebras.py

def structure_map(self) -> Morphism:
    """δ_A: W(A) → W(W(A))."""
    return self._comonad.comultiply(self._base)  # type: ignore[union-attr]

ObservedCoalgebra ¶

ObservedCoalgebra(comonad: object, carrier: SetObject, structure_tensor: Tensor, algebra: Algebra | None = None)

Bases: Coalgebra

A coalgebra defined by an explicit structure map tensor.

PARAMETER	DESCRIPTION
`comonad`	The comonad W. TYPE: `object`
`carrier`	The carrier object A. TYPE: `SetObject`
`structure_tensor`	The tensor for γ: A → W(A). TYPE: `Tensor`
`algebra`	The enrichment algebra. Defaults to PRODUCT_FUZZY. TYPE: `Algebra or None` DEFAULT: `None`

Source code in src/quivers/monadic/algebras.py

def __init__(
    self,
    comonad: object,
    carrier: SetObject,
    structure_tensor: torch.Tensor,
    algebra: VAlgebra | None = None,
) -> None:
    super().__init__(comonad, carrier)
    q = algebra if algebra is not None else PRODUCT_FUZZY
    wa = comonad.endofunctor.map_object(carrier)  # type: ignore[union-attr]
    self._morphism = observed(carrier, wa, structure_tensor, algebra=q)

structure_map ¶

structure_map() -> Morphism

The stored structure map γ: A → W(A).

Source code in src/quivers/monadic/algebras.py

def structure_map(self) -> Morphism:
    """The stored structure map γ: A → W(A)."""
    return self._morphism

EilenbergMooreCategory ¶

EilenbergMooreCategory(monad: Monad)

The Eilenberg-Moore category of a monad.

Objects are T-algebras. Morphisms (A, α) → (B, β) are base morphisms f: A → B satisfying β ∘ T(f) = f ∘ α, i.e., algebra homomorphisms.

PARAMETER	DESCRIPTION
`monad`	The underlying monad T. TYPE: `Monad`

Source code in src/quivers/monadic/algebras.py

def __init__(self, monad: Monad) -> None:
    self._monad = monad

monad `property` ¶

monad: Monad

The underlying monad.

free_algebra ¶

free_algebra(obj: SetObject) -> FreeAlgebra

Construct the free T-algebra on an object.

PARAMETER	DESCRIPTION
`obj`	The base object A. TYPE: `SetObject`

RETURNS	DESCRIPTION
`FreeAlgebra`	The free algebra with carrier T(A).

Source code in src/quivers/monadic/algebras.py

def free_algebra(self, obj: SetObject) -> FreeAlgebra:
    """Construct the free T-algebra on an object.

    Parameters
    ----------
    obj : SetObject
        The base object A.

    Returns
    -------
    FreeAlgebra
        The free algebra with carrier T(A).
    """
    return FreeAlgebra(self._monad, obj)

is_homomorphism ¶

is_homomorphism(f: Morphism, source_alg: Algebra, target_alg: Algebra, atol: float = 1e-05) -> bool

Check if f: A → B is an algebra homomorphism.

Verifies β ∘ T(f) = f ∘ α.

PARAMETER	DESCRIPTION
`f`	A morphism A → B between the carriers. TYPE: `Morphism`
`source_alg`	The source algebra (A, α). TYPE: `Algebra`
`target_alg`	The target algebra (B, β). TYPE: `Algebra`
`atol`	Absolute tolerance for comparison. TYPE: `float` DEFAULT: `1e-05`

RETURNS	DESCRIPTION
`bool`	True if f is a homomorphism within tolerance.

Source code in src/quivers/monadic/algebras.py

def is_homomorphism(
    self,
    f: Morphism,
    source_alg: VAlgebra,
    target_alg: VAlgebra,
    atol: float = 1e-5,
) -> bool:
    """Check if f: A → B is an algebra homomorphism.

    Verifies β ∘ T(f) = f ∘ α.

    Parameters
    ----------
    f : Morphism
        A morphism A → B between the carriers.
    source_alg : Algebra
        The source algebra (A, α).
    target_alg : Algebra
        The target algebra (B, β).
    atol : float
        Absolute tolerance for comparison.

    Returns
    -------
    bool
        True if f is a homomorphism within tolerance.
    """
    alpha = source_alg.structure_map()
    beta = target_alg.structure_map()
    tf = self._monad.endofunctor.map_morphism(f)

    # left: β ∘ T(f)
    left = (tf >> beta).tensor

    # right: f ∘ α
    right = (alpha >> f).tensor

    return torch.allclose(left, right, atol=atol)

Algebras and Coalgebras¶

algebras ¶

Algebra ¶

monad property ¶

carrier property ¶

structure_map abstractmethod ¶

verify_unit_law ¶

verify_associativity ¶

FreeAlgebra ¶

base property ¶

structure_map ¶

ObservedAlgebra ¶

structure_map ¶

Coalgebra ¶

comonad property ¶

carrier property ¶

structure_map abstractmethod ¶

verify_counit_law ¶

verify_coassociativity ¶

CofreeCoalgebra ¶

base property ¶

structure_map ¶

ObservedCoalgebra ¶

structure_map ¶

EilenbergMooreCategory ¶

monad property ¶

free_algebra ¶

is_homomorphism ¶

monad `property` ¶

carrier `property` ¶

structure_map `abstractmethod` ¶

base `property` ¶

comonad `property` ¶

carrier `property` ¶

structure_map `abstractmethod` ¶

base `property` ¶

monad `property` ¶