Arrow Typeclass Hierarchy

Category_, Arrow, ArrowChoice, ArrowApply, ArrowLoop, ArrowZero, ArrowPlus, the Hughes-style arrow tower.

typeclasses

Hughes-style arrow typeclass interfaces.

Each abstract typeclass declares the operations an arrow instance must provide. Concrete instances (Function, VRel, Stochastic, Kleisli(M), Cokleisli(W), LinearMap) live in quivers.arrows.instances.

References

• Hughes, J. (2000). Generalising Monads to Arrows. Science of Computer Programming, 37(1–3), 67–111. doi:10.1016/S0167-6423(99)00023-4

Category_

Bases: ABC

A category of computations.

Provides identity at every object plus binary composition. The underscore disambiguates from quivers.dsl.ast_nodes.CategoryDecl and quivers.stochastic.categories.Category which use the same word in different senses.

Laws:

• compose(id, f) = f (left identity)
• compose(f, id) = f (right identity)
• compose(compose(f, g), h) = compose(f, compose(g, h)) (associativity)

id_arr abstractmethod

id_arr(A: SetObject) -> Morphism

id_A : A ⇝ A.

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

@abstractmethod
def id_arr(self, A: SetObject) -> Morphism:
    """``id_A : A ⇝ A``."""

compose abstractmethod

compose(f: Morphism, g: Morphism) -> Morphism

f : A ⇝ B, g : B ⇝ C ⊢ g ∘ f : A ⇝ C.

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

@abstractmethod
def compose(self, f: Morphism, g: Morphism) -> Morphism:
    """``f : A ⇝ B, g : B ⇝ C  ⊢  g ∘ f : A ⇝ C``."""

Arrow

Bases: Category_, ABC

An arrow: Category_ with arr and first.

Adds:

• arr — lift a pure morphism into the arrow.
• first — apply on the left of a pair, threading a context.

Defaults derivable from these and compose: second f = swap >>> first f >>> swap; f *** g = first f >>> second g (the parallel-product combinator); f &&& g = arr (\x. (x, x)) >>> (f *** g).

Hughes 2000 §3 lists the seven arrow laws.

arr abstractmethod

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

Lift a pure morphism: arr(f) : A ⇝ B from f : A → B.

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

@abstractmethod
def arr(self, A: SetObject, B: SetObject, f: Morphism) -> Morphism:
    """Lift a pure morphism: ``arr(f) : A ⇝ B`` from ``f : A → B``."""

first abstractmethod

first(f: Morphism, C: SetObject) -> Morphism

f : A ⇝ B ⊢ first(f, C) : (A ⊗ C) ⇝ (B ⊗ C).

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

@abstractmethod
def first(self, f: Morphism, C: SetObject) -> Morphism:
    """``f : A ⇝ B  ⊢  first(f, C) : (A ⊗ C) ⇝ (B ⊗ C)``."""

ArrowChoice

Bases: Arrow, ABC

An arrow with sum-elimination: left and (derivably) right.

Adds:

• left_arr — apply on the left of a coproduct.

Derived: right_arr, +++, |||.

left_arr abstractmethod

left_arr(f: Morphism, C: SetObject) -> Morphism

f : A ⇝ B ⊢ left(f, C) : (A + C) ⇝ (B + C).

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

@abstractmethod
def left_arr(self, f: Morphism, C: SetObject) -> Morphism:
    """``f : A ⇝ B  ⊢  left(f, C) : (A + C) ⇝ (B + C)``."""

ArrowApply

Bases: Arrow, ABC

An arrow that can apply arrow-valued data: app.

ArrowApply instances are equivalent in expressive power to quivers.monadic.typeclasses.Monad; the bridges in quivers.monadic.bridges realise the conversion in both directions.

app abstractmethod

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

app : Hom(A, B) ⊗ A ⇝ B.

Hom(A, B) is the internal hom of the arrow's underlying symmetric monoidal closed structure.

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

@abstractmethod
def app(self, A: SetObject, B: SetObject) -> Morphism:
    """``app : Hom(A, B) ⊗ A ⇝ B``.

    ``Hom(A, B)`` is the internal hom of the arrow's underlying
    symmetric monoidal closed structure.
    """

ArrowLoop

Bases: Arrow, ABC

An arrow with feedback: loop.

Encodes traced symmetric monoidal structure on the arrow category.

For an arrow f : (A ⊗ C) ⇝ (B ⊗ C), loop(f) : A ⇝ B closes the loop on C. In Function, this is the least-fixed-point operator; in VRel, it is the iterative trace; in Stochastic and Kern, it is the cartesian / sampled trace.

The chart-fold parser combinator of quivers.dsl.ast_nodes.ExprChartFold is denotationally an loop_arr invocation on the appropriate arrow.

loop_arr abstractmethod

loop_arr(f: Morphism, C: SetObject) -> Morphism

f : (A ⊗ C) ⇝ (B ⊗ C) ⊢ loop(f) : A ⇝ B.

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

@abstractmethod
def loop_arr(self, f: Morphism, C: SetObject) -> Morphism:
    """``f : (A ⊗ C) ⇝ (B ⊗ C)  ⊢  loop(f) : A ⇝ B``."""

ArrowZero

Bases: Arrow, ABC

An arrow with a designated bottom at every hom: zero_arr.

zero_arr abstractmethod

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

zero : A ⇝ B — the bottom element of Hom(A, B).

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

@abstractmethod
def zero_arr(self, A: SetObject, B: SetObject) -> Morphism:
    """``zero : A ⇝ B`` — the bottom element of ``Hom(A, B)``."""

ArrowPlus

Bases: ArrowZero, ABC

An ArrowZero with pointwise alternative: alt_arr.

alt_arr plays the role of Alternative.alt lifted to the arrow category's hom-sets.

alt_arr abstractmethod

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

Hom(A, B) ⊗ Hom(A, B) ⇝ Hom(A, B).

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

@abstractmethod
def alt_arr(self, A: SetObject, B: SetObject) -> Morphism:
    """``Hom(A, B) ⊗ Hom(A, B) ⇝ Hom(A, B)``."""