Typeclass Hierarchy

Functor / Applicative / Monad / Alternative / MonadPlus / Foldable / Traversable / MonadTrans ABCs.

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)``."""