Typeclass Hierarchy

ABCs for Functor, Applicative, Monad, Alternative, MonadPlus, Foldable, Traversable, and MonadTrans.

typeclasses

Haskell-style typeclass hierarchy for compositional effects.

This module defines the abstract interfaces that effect instances implement. Each typeclass declares a set of operations that an instance must provide; default derivations are supplied where Haskell admits them. The class-extension lattice is:

Functor
├── Applicative
│   ├── Monad
│   └── Alternative
│       └── MonadPlus  (also extends Monad)
└── Traversable      (also extends Foldable)

Foldable

MonadTrans   — orthogonal: lifts an inner monad through a stacked
               transformer; not a sub-class of any of the above.

The quivers.stochastic.effect_lifts.class_directed_lifts schema-lifting machinery dispatches on which classes an effect inhabits, never on the effect's identity, so user-defined effects extend the framework automatically.

Each typeclass is also mirrored by a panproto.Theory in quivers.monadic.theories; class-extension is realised there as theory inclusion via panproto.colimit, making every instance a verifiable theory morphism.

References

• Bumford, D. and Charlow, S. (2026). Effect-Driven Interpretation: Functors for Natural Language Composition. Cambridge Elements in Semantics. Cambridge University Press. Online ISBN 9781009285377; preprint arXiv:2504.00316.
• Hughes, J. (2000). Generalising monads to arrows. Science of Computer Programming, 37(1–3), 67–111. doi:10.1016/S0167-6423(99)00023-4.
• Bauer, A. and Pretnar, M. (2015). Programming with algebraic effects and handlers. Journal of Logical and Algebraic Methods in Programming, 84(1), 108–123. doi:10.1016/j.jlamp.2014.02.001.

Functor

Bases: ABC

Functor: an endofunctor on (V-enriched) finite sets.

A Functor instance carries:

• fmap_obj — the type-level action F : SetObject → SetObject.
• fmap — the morphism-level action sending f : A → B to F(f) : F(A) → F(B).

Functor laws:

• identity: F(id_A) = id_{F(A)}
• composition: F(g ∘ f) = F(g) ∘ F(f)

Both laws are documented and runtime-checkable in quivers.monadic.laws.

fmap_obj abstractmethod

fmap_obj(A: SetObject) -> SetObject

The type-level action F(A).

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

@abstractmethod
def fmap_obj(self, A: SetObject) -> SetObject:
    """The type-level action ``F(A)``."""

fmap abstractmethod

fmap(A: SetObject, B: SetObject, f: Morphism) -> Morphism

The morphism-level action F(f) : F(A) → F(B).

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

@abstractmethod
def fmap(self, A: SetObject, B: SetObject, f: Morphism) -> Morphism:
    """The morphism-level action ``F(f) : F(A) → F(B)``."""

Applicative

Bases: Functor, ABC

Applicative functor: pure + apply.

Adds:

• pure — the unit η_A : A → F(A).
• apply — the application combinator F(A → B) ⊗ F(A) → F(B).

Applicative laws (Hughes 2000 §3.1, after McBride and Paterson):

• identity: apply(pure(id), v) = v
• homomorphism: apply(pure(f), pure(x)) = pure(f x)
• interchange: apply(u, pure(y)) = apply(pure(λf. f y), u)
• composition: apply(apply(apply(pure(∘), u), v), w) = apply(u, apply(v, w))

The default fmap derivation fmap(f) = apply(pure(f), -) is provided.

pure abstractmethod

pure(A: SetObject) -> Morphism

η_A : A → F(A).

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

@abstractmethod
def pure(self, A: SetObject) -> Morphism:
    """``η_A : A → F(A)``."""

apply

apply(A: SetObject, B: SetObject) -> Morphism

F(A → B) ⊗ F(A) → F(B).

Realised in V-Rel as a parameterized binary operation; the concrete construction depends on the instance and on the internal-hom representation of the underlying enriched category. The default implementation raises NotImplementedError; concrete instances override.

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

def apply(self, A: SetObject, B: SetObject) -> Morphism:
    """``F(A → B) ⊗ F(A) → F(B)``.

    Realised in V-Rel as a parameterized binary operation; the
    concrete construction depends on the instance and on the
    internal-hom representation of the underlying enriched
    category. The default implementation raises
    `NotImplementedError`; concrete instances override.
    """
    raise NotImplementedError(
        f"{type(self).__name__}.apply requires an internal-hom "
        "construction; override on the concrete instance"
    )

lift_a2

lift_a2(A: SetObject, B: SetObject, C: SetObject, f: Morphism) -> Morphism

Apply a binary function under the Applicative.

Default derivation: liftA2 f x y = apply(apply(pure f, x), y). Concrete instances may override for efficiency.

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

def lift_a2(
    self, A: SetObject, B: SetObject, C: SetObject, f: Morphism
) -> Morphism:
    """Apply a binary function under the Applicative.

    Default derivation: ``liftA2 f x y = apply(apply(pure f, x), y)``.
    Concrete instances may override for efficiency.
    """
    raise NotImplementedError(
        "lift_a2 default derivation requires a panproto-side "
        "currying construction; override on the concrete instance"
    )

Monad

Bases: Applicative, ABC

Monad: pure + join (or bind).

Adds:

• join — the multiplication μ_A : F(F(A)) → F(A).

The bind operation is derived via bind(m, k) = join(fmap(k)(m)).

Monad laws:

• left unit: bind(pure(a), k) = k(a)
• right unit: bind(m, pure) = m
• associativity: bind(bind(m, k), h) = bind(m, λx. bind(k(x), h))

These are equivalent to:

• join ∘ pure_F = id (left unit)
• join ∘ F(pure) = id (right unit)
• join ∘ F(join) = join ∘ join (associativity)

join abstractmethod

join(A: SetObject) -> Morphism

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

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

@abstractmethod
def join(self, A: SetObject) -> Morphism:
    """``μ_A : F(F(A)) → F(A)``."""

bind

bind(A: SetObject, B: SetObject, k: Morphism) -> Morphism

Monadic bind: F(A) ⊗ (A → F(B)) → F(B).

Default derivation: bind(m, k) = join_B(fmap(k)(m)). Override on the concrete instance for a more direct realisation.

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

def bind(self, A: SetObject, B: SetObject, k: Morphism) -> Morphism:
    """Monadic bind: ``F(A) ⊗ (A → F(B)) → F(B)``.

    Default derivation: ``bind(m, k) = join_B(fmap(k)(m))``. Override
    on the concrete instance for a more direct realisation.
    """
    raise NotImplementedError(
        "bind default derivation requires panproto-side composition; "
        "override on the concrete instance"
    )

Alternative

Bases: Applicative, ABC

Alternative: an Applicative with empty + alt.

Adds:

• empty — the bottom element ⊥_A : 1 → F(A).
• alt — pointwise alternative F(A) ⊗ F(A) → F(A).

Alternative laws:

• identity: alt(empty, x) = x = alt(x, empty)
• associativity: alt(alt(x, y), z) = alt(x, alt(y, z))
• left zero (when also a Monad): bind(empty, k) = empty

empty abstractmethod

empty(A: SetObject) -> Morphism

⊥_A : 1 → F(A).

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

@abstractmethod
def empty(self, A: SetObject) -> Morphism:
    """``⊥_A : 1 → F(A)``."""

alt abstractmethod

alt(A: SetObject) -> Morphism

F(A) ⊗ F(A) → F(A).

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

@abstractmethod
def alt(self, A: SetObject) -> Morphism:
    """``F(A) ⊗ F(A) → F(A)``."""

MonadPlus

Bases: Monad, Alternative, ABC

Monad + Alternative: a Monad whose F is also Alternative.

No new operations; the diamond inheritance picks up both join (from Monad) and empty / alt (from Alternative). Adds the left-zero law: bind(empty, k) = empty (already documented under Alternative).

Foldable

Bases: ABC

Foldable: support a catamorphism-like fold.

Used by Hamblin-style alternative semantics to collapse a structure of alternatives down to a single value. The minimal interface is foldr; richer combinators are derivable.

foldr abstractmethod

foldr(A: SetObject, B: SetObject) -> Morphism

(A ⊗ B → B) ⊗ B ⊗ F(A) → B.

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

@abstractmethod
def foldr(self, A: SetObject, B: SetObject) -> Morphism:
    """``(A ⊗ B → B) ⊗ B ⊗ F(A) → B``."""

Traversable

Bases: Functor, Foldable, ABC

Traversable: distribute an Applicative action through a structure.

Adds traverse: given an Applicative G and a morphism f : A → G(B), produces F(A) → G(F(B)). This is Charlow's central tool for distributing scope through alternatives.

Traversable laws (after McBride and Paterson 2008):

• naturality: t ∘ traverse(f) = traverse(t ∘ f) for any applicative natural transformation t.
• identity: traverse(pure_Identity) = pure_Identity
• composition: traverse(Compose ∘ f) = Compose ∘ fmap(traverse(g)) ∘ traverse(f)

traverse abstractmethod

traverse(A: SetObject, B: SetObject, applicative: Applicative, f: Morphism) -> Morphism

F(A) → G(F(B)) for an Applicative G and f : A → G(B).

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

@abstractmethod
def traverse(
    self, A: SetObject, B: SetObject, applicative: Applicative, f: Morphism
) -> Morphism:
    """``F(A) → G(F(B))`` for an Applicative ``G`` and ``f : A → G(B)``."""

MonadTrans

Bases: ABC

Monad transformer: lift an inner monad to a stacked monad.

A MonadTrans instance T provides lift, embedding an inner-monad Kleisli arrow into the transformer. The class is orthogonal to the Functor/Applicative/Monad tower: transformers are themselves monads (when applied to a base monad), but the transformer interface is the lift, not the bind.

Lift laws:

• lift ∘ pure_m = pure_{T(m)}
• lift(bind_m(x, k)) = bind_{T(m)}(lift(x), lift ∘ k)

lift abstractmethod

lift(m: Monad, A: SetObject) -> Morphism

m(A) → T(m)(A).

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

@abstractmethod
def lift(self, m: Monad, A: SetObject) -> Morphism:
    """``m(A) → T(m)(A)``."""

Package constants

The typeclass theories of quivers.monadic, each a TypeclassTheory.

Monadic structures: typeclass hierarchy, instances, transformers, algebraic effects, comonads, algebras, and distributive laws.

The Monad ABC lives in typeclasses. Concrete monad implementations (FuzzyPowersetMonad, FreeMonoidMonad, GiryMonad, etc.) subclass it directly and provide the fmap_obj / fmap / pure / apply / join operations. unit and multiply are exposed as aliases on the concrete classes for the Eilenberg–Moore vocabulary.

ThFunctor module-attribute

ThFunctor = TypeclassTheory(name='ThFunctor', sorts=('Carrier', 'Hom'), operations=('fmap_obj : Carrier → Carrier', 'fmap : Hom → Hom'), equations=('fmap(id) = id', 'fmap(g ∘ f) = fmap(g) ∘ fmap(f)'))

The theory of Functor.

ThApplicative module-attribute

ThApplicative = TypeclassTheory(name='ThApplicative', operations=('pure : Carrier → F(Carrier)', 'apply : F(Hom) ⊗ F(Carrier) → F(Carrier)'), equations=('apply(pure(id), v) = v', 'apply(pure(f), pure(x)) = pure(f x)', 'apply(u, pure(y)) = apply(pure(λf. f y), u)', 'apply(apply(apply(pure(∘), u), v), w) = apply(u, apply(v, w))'), extends=('ThFunctor',))

The theory of Applicative.

ThMonad module-attribute

ThMonad = TypeclassTheory(name='ThMonad', operations=('join : F(F(Carrier)) → F(Carrier)',), equations=('join ∘ pure = id', 'join ∘ fmap(pure) = id', 'join ∘ fmap(join) = join ∘ join'), extends=('ThApplicative',))

The theory of Monad.

ThAlternative module-attribute

ThAlternative = TypeclassTheory(name='ThAlternative', operations=('empty : 1 → F(Carrier)', 'alt : F(Carrier) ⊗ F(Carrier) → F(Carrier)'), equations=('alt(empty, x) = x', 'alt(x, empty) = x', 'alt(alt(x, y), z) = alt(x, alt(y, z))'), extends=('ThApplicative',))

The theory of Alternative.

ThMonadPlus module-attribute

ThMonadPlus = TypeclassTheory(name='ThMonadPlus', equations=('bind(empty, k) = empty',), extends=('ThMonad', 'ThAlternative'))

The theory of MonadPlus.

ThMonadTrans module-attribute

ThMonadTrans = TypeclassTheory(name='ThMonadTrans', operations=('lift : m(Carrier) → t(m)(Carrier)',), equations=('lift ∘ pure_m = pure_{T(m)}', 'lift(bind_m(x, k)) = bind_{T(m)}(lift(x), lift ∘ k)'))

The theory of MonadTrans.

ThFoldable module-attribute

ThFoldable = TypeclassTheory(name='ThFoldable', operations=('foldr : (Carrier ⊗ B → B) ⊗ B ⊗ F(Carrier) → B',))

The theory of Foldable.

ThTraversable module-attribute

ThTraversable = TypeclassTheory(name='ThTraversable', operations=('traverse : (A → G(B)) ⊗ F(A) → G(F(B))',), equations=('naturality: t ∘ traverse(f) = traverse(t ∘ f)', 'identity: traverse(pure_Identity) = pure_Identity', 'composition: traverse(Compose ∘ f) = Compose ∘ fmap(traverse(g)) ∘ traverse(f)'), extends=('ThFunctor', 'ThFoldable'))

The theory of Traversable.