"""
The abstract base classes for categories.
These mirror the concrete hierarchy of :mod:`discopy` modules: each class adds
the characteristic generator of its categorical structure as an
:func:`abc.abstractmethod`, e.g. :class:`BraidedCategory` is a
:class:`MonoidalCategory` with an abstract :meth:`BraidedCategory.braid`.
.. raw:: html
:file: api/architecture.html
Software dependencies between modules go top-to-bottom, left-to-right and
forgetful functors between categories go the other way.
Each class also declares its :func:`discopy.testable.axiom` equations, which
every free category inherits along with the structure they axiomatise:
:class:`Category` states the unitality and associativity of composition,
the typing of its identities and composites, and the involution and
contravariance of its dagger; a :class:`ColouredMonoid` inherits them as
the unitality and associativity of its product, its composition.
Summary
-------
.. autosummary::
:template: class.rst
:nosignatures:
:toctree:
Category
ColouredMonoid
Monoid
Nat
MonoidalCategory
PRO
TracedCategory
ResiduatedMonoid
BiclosedCategory
Pregroup
RigidCategory
PivotalCategory
BraidedCategory
PROB
SymmetricCategory
PROP
MarkovCategory
ClosedCategory
FeedbackCategory
BalancedCategory
RibbonCategory
CompactCategory
HypergraphCategory
NamedGeneric
"""
from __future__ import annotations
from abc import ABC, abstractmethod
from collections.abc import Sequence
from dataclasses import dataclass
from typing import ClassVar
from discopy.testable import (
Axiom, ComposablePair, ComposableTriple, Equation, axiom)
from discopy.utils import ( # noqa: F401 pylint: disable=unused-import
NamedGeneric, classproperty)
[docs]
class Category[C0, C1: Category](ABC):
"""
A category is a class with two class variables ``ob, ar``, two attributes
``dom, cod`` and two methods ``id, then``.
This base class also implements syntactic sugar :code:`>>` and :code:`<<`
for forward and backward composition with the method :code:`then`.
Example
-------
>>> class List(list, Category):
... ob, dom, cod = type(None), None, None
... def then(self, other):
... return self + other
>>> assert List([1, 2]) >> List([3]) == List([1, 2, 3])
>>> assert List([3]) << List([1, 2]) == List([1, 2, 3])
"""
ob: ClassVar[type[C0]]
factory: ClassVar[type[C1]]
dom: C0
cod: C0
#: Backward-compatible alias for :attr:`factory`, since types are
#: themselves the objects of diagrams.
ar = classproperty(lambda cls: getattr(cls, "factory", cls))
[docs]
@classmethod
def equation_factory(cls, *terms) -> Equation:
"""
Construct an equation, using strict equality by default.
A class that quotients its equations overrides this, e.g. by
hypergraph isomorphism from symmetric categories on, so an axiom
built with it is checked up to whatever quotient the category
defines — and :meth:`discopy.testable.Axiom.modulo` weakens it
further.
"""
return Equation(*terms)
@classproperty
def axioms(cls) -> dict[str, Axiom]:
"""
The axioms inherited by ``cls``, by name, subclasses overriding bases.
Names are collected before they are filtered, so that assigning
anything that is not an axiom over an inherited one drops it
altogether, rather than restating it.
"""
visible = {
name: value
for base in reversed(cls.__mro__)
for name, value in base.__dict__.items()}
return {name: value.bind(cls) for name, value in visible.items()
if isinstance(value, Axiom)}
[docs]
@classmethod
@abstractmethod
def id(cls, dom: C0) -> C1:
"""
Identity morphism on an object :code:`dom: C0`, to be instantiated.
Parameters:
dom (C0) : The domain of an identity is also its codomain.
"""
[docs]
@abstractmethod
def then(self, *others: C1) -> C1:
"""
Sequential composition of `n >= 1` morphisms, to be instantiated.
Parameters:
other : The other morphism to compose sequentially.
"""
[docs]
def is_composable(self, other: C1) -> bool:
"""
Whether two morphisms are composable, i.e. the codomain of the first is
the domain of the second.
Parameters:
other : The other morphism.
"""
return self.cod == other.dom
[docs]
def is_parallel(self, other: Category) -> bool:
"""
Whether two morphisms are parallel, i.e. they have the same
domain and codomain.
Parameters:
other : The other morphism.
"""
return (self.dom, self.cod) == (other.dom, other.cod)
@axiom
def unitality(
cls, f: C1) -> Equation[C1]:
""" Left and right unitality of composition. """
return cls.equation_factory(
cls.id(f.dom).then(f), f, f.then(cls.id(f.cod)))
@axiom
def associativity(
cls, triple: ComposableTriple[C1]) -> Equation[C1]:
""" Associativity of composition. """
f, g, h = triple
return cls.equation_factory(
f.then(g).then(h), f.then(g.then(h)))
@axiom
def identity_typing(
cls, x: C0) -> Equation[C0]:
""" Typing of identity morphisms. """
identity = cls.id(x)
return cls.ob.equation_factory(identity.dom, x, identity.cod)
@axiom
def composition_dom_typing(
cls, pair: ComposablePair[C1]) -> Equation[C0]:
""" Domain typing of composition. """
f, g = pair
return cls.ob.equation_factory(f.then(g).dom, f.dom)
@axiom
def composition_cod_typing(
cls, pair: ComposablePair[C1]) -> Equation[C0]:
""" Codomain typing of composition. """
f, g = pair
return cls.ob.equation_factory(f.then(g).cod, g.cod)
@axiom
def dagger_involution(
cls, f: C1) -> Equation[C1]:
""" The dagger is involutive. """
return cls.equation_factory(f.dagger().dagger(), f)
@axiom
def dagger_contravariance(
cls, pair: ComposablePair[C1]) -> Equation[C1]:
""" The dagger reverses composition. """
f, g = pair
return cls.equation_factory(
f.then(g).dagger(), g.dagger().then(f.dagger()))
__rshift__ = __llshift__ = lambda self, other: self.then(other)
__lshift__ = __lrshift__ = lambda self, other: other.then(self)
[docs]
class ColouredMonoid[C0, C1: ColouredMonoid](Category[C0, C1]):
"""
A coloured monoid is a category whose sequential composition ``then`` is
given by a monoidal ``tensor``, with the objects ``C0`` (its colours) as
the boundaries of its morphisms.
An ordinary :obj:`Monoid` is the special case with a single, trivial
colour, i.e. :class:`type(None)`. We do not enforce this so
that e.g. :class:`monoidal.Ty` can take colours as objects.
"""
[docs]
@classmethod
def id(cls, dom: C0 = None) -> C1:
"""The monoidal unit, i.e. the empty tensor ``cls()``."""
return cls()
[docs]
@classmethod
def unit(cls, colour: C0 = None) -> C0 | C1:
"""
The unit at a colour, i.e. the identity on it.
It need not be an element of the monoid, which is why it may land in
``C0``: the layers of :class:`monoidal.Layer` are closed under
``tensor`` but the empty one is a type rather than a layer.
"""
return cls.id(colour)
[docs]
@abstractmethod
def tensor(self, *objects: C1) -> C1:
""" The n-ary product of a monoid for ``n > 0``. """
[docs]
def then(self, *others: C1) -> C1:
"""Sequential composition, given by the monoid product."""
return self.tensor(*others)
[docs]
@classmethod
def cast(cls, atoms) -> C1:
"""
The element of a tuple of atoms, or of a single atom; an element of
the monoid is unchanged.
Parameters:
atoms : An element, a tuple of atoms or a single atom.
>>> assert Nat.cast(2) == Nat(2) == Nat.cast(Nat(2))
"""
if isinstance(atoms, cls):
return atoms
return cls(*atoms) if isinstance(atoms, tuple) else cls(atoms)
[docs]
@classmethod
def whisker(cls, other: C0 | C1) -> C1:
"""
Do nothing if ``other`` is already a morphism else apply :meth:`id`.
Parameters:
other : The object or morphism to be tensored on the left or right.
"""
return other if isinstance(other, cls) else cls.id(other)
def __matmul__(self, other):
return self.tensor(other)
def __rmatmul__(self, other):
return self.whisker(other).tensor(self)
[docs]
class Monoid[C1: Monoid](ColouredMonoid[type(None), C1]):
""" A monoid is a coloured monoid with a single, trivial colour. """
[docs]
@dataclass
class Nat(Monoid["Nat"]):
"""
``Nat`` is the free monoid on one generator, i.e. the natural numbers
with addition as tensor. It is also a sequence over its unary encoding:
:meth:`__len__` gives back the natural number itself and slicing reads
it off as a sequence of ``1``'s, e.g. ``Nat(3)[:1] == Nat(1)``.
Parameters:
n : The natural number.
"""
n: int = 0
def tensor(self, *others: Nat) -> Nat:
if any(not isinstance(other, Nat) for other in others):
return NotImplemented # This allows whiskering on the left.
return type(self)(self.n + sum(other.n for other in others))
def __len__(self) -> int:
return self.n
def __index__(self) -> int:
return self.n
def __str__(self) -> str:
return str(self.n)
def __getitem__(self, key: int | slice) -> Nat:
"""
Slicing a natural number reads it off as a sequence of ``1``'s.
Parameters:
key : An integer or a slice.
"""
if isinstance(key, slice):
return type(self)(len(range(self.n)[key]))
if key >= self.n or key < -self.n:
raise IndexError
return type(self)(1)
[docs]
class MonoidalCategory[C0: ColouredMonoid, C1: MonoidalCategory](
Category[C0, C1]):
"""
A monoidal category is a :class:`Category` with a method :code:`tensor` for
both its objects and its morphisms.
This base class also implements syntactic sugar :code:`@` for whiskering.
"""
[docs]
@classmethod
@abstractmethod
def tensor(cls, *morphisms: C1) -> C1:
"""
Parallel composition of ``n >= 0`` morphisms, to be instantiated.
Parameters:
other : The other morphism to compose in parallel.
"""
[docs]
@classmethod
def whisker(cls, other: C0 | C1) -> C1:
"""
Do nothing if ``other`` is already a morphism else apply :meth:`id`.
Parameters:
other : The object or morphism to be tensored on the left or right.
"""
return other if isinstance(other, MonoidalCategory) else cls.id(other)
def __matmul__(self, other):
return self.tensor(self.whisker(other))
def __rmatmul__(self, other):
return self.whisker(other).tensor(self)
[docs]
class PRO[C1: PRO](MonoidalCategory[Nat, C1]):
"""
A PRO is a :class:`MonoidalCategory` whose objects are the natural
numbers :class:`Nat`, i.e. the free monoidal category on one generator.
"""
[docs]
class TracedCategory[C0, C1](MonoidalCategory[C0, C1]):
"""
A traced category is a :class:`MonoidalCategory` with a method
:code:`trace` for the partial trace of a morphism over some objects.
"""
[docs]
@abstractmethod
def trace(self, n: int = 1, left: bool = False) -> C1:
"""
The trace of a morphism, to be instantiated.
Tracing no object at all is the identity, i.e. the vanishing axiom
``f.trace(0) == f``, see `nLab
<https://ncatlab.org/nlab/show/traced+monoidal+category>`_.
Parameters:
n : The number of objects to trace over.
left : Whether to trace the wires on the left or right.
"""
[docs]
class ResiduatedMonoid[C0, C1: ResiduatedMonoid](ColouredMonoid[C0, C1]):
"""
A monoid is residuated when it comes with methods ``over`` and ``under``
with syntactic sugar ``<<`` and ``>>``.
"""
[docs]
@abstractmethod
def over(self, other: C1) -> C1:
""" The right-to-left exponential object ``self`` to the ``other``. """
[docs]
@abstractmethod
def under(self, other: C1) -> C1:
""" The left-to-right exponential object ``self`` to the ``other``. """
def __lshift__(self, other):
return self.over(other)
def __rshift__(self, other):
return other.under(self)
[docs]
class BiclosedCategory[
C0: ResiduatedMonoid, C1: BiclosedCategory](MonoidalCategory[C0, C1]):
"""
A biclosed category is a :class:`MonoidalCategory` with methods :code:`ev`
and :code:`curry` for the evaluation and currying of morphisms.
We also assume the type for objects comes with methods for left and right
exponentials :code`x << y` and :code`x >> y`.
"""
[docs]
@classmethod
@abstractmethod
def ev(cls, base: C0, exponent: C0, left: bool = True) -> C1:
"""
The evaluation of an exponential type, to be instantiated.
Parameters:
base : The base of the exponential type.
exponent : The exponent of the exponential type.
left : Whether to take the left or right evaluation.
"""
[docs]
@abstractmethod
def curry(self, n: int = 1, left: bool = True) -> C1:
"""
The currying of a morphism, to be instantiated.
Parameters:
n : The number of objects to curry.
left : Whether to curry on the left or right.
"""
[docs]
def base_and_exponent(self, n: int, left: bool) -> tuple[C0, C0]:
"""
The base and exponent that :meth:`uncurry` evaluates, read off the
exponential object in the codomain.
Parameters:
n : The number of objects to uncurry.
left : Whether to uncurry on the left or right.
"""
# pylint: disable=unused-argument # the exponential says the side
if not self.cod.is_exp:
raise ValueError
base, exponent = self.cod.base, self.cod.exponent
if n < len(exponent):
raise ValueError
return base, exponent
[docs]
def uncurry(self, n: int = 1, left: bool = True) -> C1:
"""
Uncurry a morphism by composing it with :meth:`ev`, assuming its
codomain is an exponential object. If the exponent has less than
``n`` objects, we uncurry the remaining ones in turn.
Parameters:
n : The number of objects to uncurry.
left : Whether to uncurry on the left or right.
"""
if n < 0:
raise ValueError
if not n:
return self
base, exponent = self.base_and_exponent(n, left)
result = self @ exponent >> self.ev(base, exponent, True) if left\
else exponent @ self >> self.ev(base, exponent, False)
return result.uncurry(n - len(exponent), left)
[docs]
class Pregroup[C0, C1: Pregroup](ResiduatedMonoid[C0, C1]):
"""
A pregroup is a residuated monoid where the left and right exponentials are
given by tensoring with the chosen left and right duals for each object.
"""
l: C1
r: C1
def over(self, other: C1) -> C1:
return self @ other.l
def under(self, other: C1) -> C1:
return other.r @ self
[docs]
class RigidCategory[C0: Pregroup, C1: RigidCategory](BiclosedCategory[C0, C1]):
"""
A rigid category is a :class:`BiclosedCategory` with a :class:`Pregroup` as
object type and methods for :code:`cups` and :code:`caps`.
"""
[docs]
@classmethod
@abstractmethod
def cups(cls, left: C0, right: C0) -> C1:
"""
The cups witnessing :code:`right` as the adjoint of :code:`left`.
Parameters:
left : The left-hand side of the cups.
right : Its adjoint, i.e. the right-hand side of the cups.
"""
[docs]
@classmethod
@abstractmethod
def caps(cls, left: C0, right: C0) -> C1:
"""
The caps witnessing :code:`right` as the adjoint of :code:`left`.
Parameters:
left : The left-hand side of the caps.
right : Its adjoint, i.e. the right-hand side of the caps.
"""
[docs]
@classmethod
def ev(cls, base: C0, exponent: C0, left: bool = True) -> C1:
"""
The evaluation of a rigid morphism is obtained using cups.
Parameters:
base : The base of the exponential type.
exponent : The exponent of the exponential type.
left : Whether to take the left or right evaluation.
"""
return base @ cls.cups(exponent.l, exponent) if left\
else cls.cups(exponent, exponent.r) @ base
[docs]
def curry(self, n: int = 1, left: bool = True) -> C1:
"""
The curry of a rigid morphism is obtained using caps.
Parameters:
n : The number of objects to curry.
left : Whether to curry on the left or right.
"""
if n < 0 or n > len(self.dom):
raise ValueError
if not n:
return self
if left:
base, exponent = self.dom[:-n], self.dom[-n:]
return base @ self.caps(exponent, exponent.l) >> self @ exponent.l
base, exponent = self.dom[n:], self.dom[:n]
return self.caps(exponent.r, exponent) @ base >> exponent.r @ self
[docs]
def base_and_exponent(self, n: int, left: bool) -> tuple[C0, C0]:
"""
Contrary to :meth:`BiclosedCategory.base_and_exponent`, a pregroup has
no exponential object to read the exponent off the codomain: it is the
``n`` objects at the end resp. the start of the codomain, dualised.
Parameters:
n : The number of objects to uncurry.
left : Whether to uncurry on the left or right.
"""
if n > len(self.cod):
raise ValueError
return (self.cod[:-n], self.cod[-n:].r) if left\
else (self.cod[n:], self.cod[:n].l)
[docs]
def transpose(self, left: bool = False) -> C1:
"""
The transpose of a morphism, i.e. its composition with cups and caps.
Parameters:
left : Whether to transpose left or right.
Example
-------
>>> from discopy.monoidal import Equation
>>> from discopy.rigid import Ty, Box
>>> x, y = map(Ty, "xy")
>>> f = Box('f', x, y)
>>> Equation(f.transpose(left=True), f, f.transpose(),
... symbols=("$\\\\mapsfrom$", "$\\\\mapsto$")).draw(
... figsize=(8, 3), doctest="docs/_static/rigid/transpose.svg")
.. image:: /_static/rigid/transpose.svg
"""
if left:
return self.cod.l @ self.caps(self.dom, self.dom.l)\
>> self.cod.l @ self @ self.dom.l\
>> self.cups(self.cod.l, self.cod) @ self.dom.l
return self.caps(self.dom.r, self.dom) @ self.cod.r\
>> self.dom.r @ self @ self.cod.r\
>> self.dom.r @ self.cups(self.cod, self.cod.r)
[docs]
class PivotalCategory[C0, C1](RigidCategory[C0, C1], TracedCategory[C0, C1]):
"""
A pivotal category is a :class:`RigidCategory` where the left and right
adjoints coincide, hence it is also a :class:`TracedCategory`.
"""
[docs]
class BraidedCategory[C0, C1](MonoidalCategory[C0, C1]):
"""
A braided category is a :class:`MonoidalCategory` with a method
:code:`braid` for the natural isomorphism :code:`x @ y -> y @ x`.
"""
[docs]
@classmethod
@abstractmethod
def braid(cls, left: C0, right: C0) -> C1:
"""
The braid of two objects, to be instantiated.
Parameters:
left : The object on the left of the braid.
right : The object on the right of the braid.
"""
[docs]
class PROB[C1: PROB](PRO[C1], BraidedCategory[Nat, C1]):
"""
A PROB is a :class:`BraidedCategory` whose objects are the natural
numbers :class:`Nat`, i.e. the free braided category on one generator.
"""
[docs]
class SymmetricCategory[C0, C1](BraidedCategory[C0, C1]):
"""
A symmetric category is a :class:`BraidedCategory` where the braid is its
own inverse called :code:`swap` for the symmetry :code:`x @ y -> y @ x`.
"""
[docs]
@classmethod
@abstractmethod
def swap(cls, left: C0, right: C0) -> C1:
"""
The swap of two objects, to be instantiated.
Parameters:
left : The object on the left of the swap.
right : The object on the right of the swap.
"""
[docs]
@classmethod
def permutation(cls, xs: Sequence[int], doms: Sequence[C0]) -> C1:
""" Compose swaps to permute the atomic objects in ``dom``. """
xs, doms = list(xs), list(doms)
if list(range(len(doms))) != sorted(xs):
raise ValueError
tensor = lambda objects: cls.ob().tensor(*objects)
result, done = cls.id(tensor(doms)), cls.ob()
while xs != list(range(len(xs))):
i = xs[0]
left, head = tensor(doms[:i]), tensor(doms[i:i + 1])
result >>= done @ cls.swap(left, head) @ tensor(doms[i + 1:])
done, doms = done @ head, doms[:i] + doms[i + 1:]
xs = [x - 1 if x > i else x for x in xs[1:]]
return result
@classmethod
def braid(cls, left: C0, right: C0) -> C1:
return cls.swap(left, right)
[docs]
class PROP[C1: PROP](PROB[C1], SymmetricCategory[Nat, C1]):
"""
A PROP is a :class:`SymmetricCategory` whose objects are the natural
numbers :class:`Nat`, i.e. the free symmetric category on one generator.
"""
[docs]
class MarkovCategory[C0, C1](SymmetricCategory[C0, C1]):
"""
A Markov category is a :class:`SymmetricCategory` with methods
:code:`copy` and :code:`merge` for the supply of commutative comonoids.
"""
[docs]
@classmethod
@abstractmethod
def copy(cls, x: C0, n: int = 2) -> C1:
"""
Make :code:`n` copies of a given object :code:`x`.
Parameters:
x : The object to copy.
n : The number of copies.
"""
[docs]
class ClosedCategory[C0, C1](BiclosedCategory[C0, C1], MarkovCategory[C0, C1]):
"""
A closed category is a symmetric :class:`BiclosedCategory`. We also assume
it comes with copy and discard so it is also a :class:`MarkovCategory`.
"""
[docs]
class FeedbackCategory[C0, C1](MarkovCategory[C0, C1]):
"""
A feedback category is a :class:`MarkovCategory` with a :code:`delay`
endofunctor and a :code:`feedback` operator.
"""
[docs]
@abstractmethod
def delay(self, n_steps: int = 1) -> C1:
"""
The delay endofunctor applied to a morphism.
Parameters:
n_steps : The number of time steps to delay.
"""
[docs]
@abstractmethod
def feedback(self, dom: C0, cod: C0, mem: C0) -> C1:
"""
The feedback operator on a morphism.
Parameters:
dom : The domain of the feedback.
cod : The codomain of the feedback.
mem : The memory type to trace over.
"""
[docs]
class BalancedCategory[C0, C1](
BraidedCategory[C0, C1], TracedCategory[C0, C1]):
"""
A balanced category is a :class:`BraidedCategory` and a
:class:`TracedCategory` with a method :code:`twist` for the natural
automorphism :code:`x -> x`.
"""
[docs]
@classmethod
@abstractmethod
def twist(cls, dom: C0) -> C1:
"""
The twist on an object, to be instantiated.
Parameters:
dom : The object on which to take the twist.
"""
[docs]
class RibbonCategory[C0, C1](
PivotalCategory[C0, C1], BalancedCategory[C0, C1]):
"""
A ribbon category is a :class:`PivotalCategory` which is also a
:class:`BalancedCategory`, i.e. where diagrams can draw knots and links.
"""
[docs]
class CompactCategory[C0, C1](
RibbonCategory[C0, C1], SymmetricCategory[C0, C1]):
"""
A compact category is a :class:`RibbonCategory` which is also a
:class:`SymmetricCategory`, i.e. with cups, caps and swaps and where
the twist is the identity.
"""
@classmethod
def twist(cls, dom: C0) -> C1:
return cls.id(dom)
[docs]
class HypergraphCategory[C0, C1](
CompactCategory[C0, C1], MarkovCategory[C0, C1]):
"""
A hypergraph category is a symmetric category with a supply of spiders,
i.e. special commutative Frobenius algebras on each objects.
This makes it both a :class:`CompactCategory` and a :class:`MarkovCategory`
"""
[docs]
@classmethod
@abstractmethod
def spiders(cls, n_legs_in: int, n_legs_out: int, typ: C0) -> C1:
"""
The spiders on a given type with ``n_legs_in`` and ``n_legs_out``.
Parameters:
n_legs_in : The number of legs in for each spider.
n_legs_out : The number of legs out for each spider.
typ : The type of the spiders.
"""