Categorical algebra

Free diagrams in a category.

A free diagram in a category is a diagram whose shape is a free category. Examples include the empty diagram, pairs of objects, discrete diagrams, parallel morphisms, spans, and cospans. Limits and colimits are most commonly taken over free diagrams.

A free diagram that is bipartite.

Such diagrams include most of the fixed shapes, such as spans, cospans, and parallel morphisms. They are the generic shape of diagrams for limits and colimits arising from undirected wiring diagrams. For limits, the boxes correspond to vertices in $V₁$ and the junctions to vertics in $V₂$. Colimits are dual.

Cospan of morphisms in a category.

A common special case of Multicospan. See also Span.

Discrete diagram: a diagram whose only morphisms are identities.

Abstract type for free diagram of fixed shape.

Multicospan of morphisms in a category.

A multicospan is like a Cospan except that it may have a number of legs different than two. A limit of this shape is a pullback.

Multispan of morphisms in a category.

A multispan is like a Span except that it may have a number of legs different than two. A colimit of this shape is a pushout.

Parallel morphims in a category.

Parallel morphisms are just morphisms with the same domain and codomain. A (co)limit of this shape is a (co)equalizer.

For the common special case of two morphisms, see ParallelPair.

Pair of parallel morphisms in a category.

A common special case of ParallelMorphisms.

Span of morphims in a category.

A common special case of Multispan. See also Cospan.

Bundle together legs of a multi(co)span.

For example, calling bundle_legs(span, SVector((1,2),(3,4))) on a multispan with four legs gives a span whose left leg bundles legs 1 and 2 and whose right leg bundles legs 3 and 4. Note that in addition to bundling, this function can also permute legs and discard them.

The bundling is performed using the universal property of (co)products, which assumes that these (co)limits exist.

Limits and colimits in a category.

Abstract type for colimit in a category.

The standard concrete subtype is Colimit, although for computational reasons certain categories may use different subtypes to include extra data.

Abstract type for limit in a category.

The standard concrete subtype is Limit, although for computational reasons certain categories may use different subtypes to include extra data.

Colimit in a category.

Algorithm for computing colimits.

Compute pushout by composing a coproduct with a coequalizer.

See also: ComposeProductEqualizer.

Compute pullback by composing a product with an equalizer.

See also: ComposeCoproductCoequalizer.

Limit in a category.

Algorithm for computing limits.

Colimit of a diagram.

To define colimits in a category with objects Ob, override the method colimit(::FreeDiagram{Ob}) for general colimits or colimit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for colimits of specific shape, such as coproducts or coequalizers.

See also: limit

Limit of a diagram.

To define limits in a category with objects Ob, override the method limit(::FreeDiagram{Ob}) for general limits or limit(::D) with suitable type D <: FixedShapeFreeDiagram{Ob} for limits of specific shape, such as products or equalizers.

See also: colimit

Pullback of a pair of morphisms with common codomain.

To implement for a type T, define the method limit(::Cospan{T}) and/or limit(::Multicospan{T}) or, if you have already implemented products and equalizers, rely on the default implementation.

Pushout of a pair of morphisms with common domain.

To implement for a type T, define the method colimit(::Span{T}) and/or colimit(::Multispan{T}) or, if you have already implemented coproducts and coequalizers, rely on the default implementation.

Universal property of (co)limits.

Compute the morphism whose existence and uniqueness is guaranteed by the universal property of (co)limits.

See also: limit, colimit.

Coequalizer of morphisms with common domain and codomain.

To implement for a type T, define the method colimit(::ParallelPair{T}) or colimit(::ParallelMorphisms{T}).

Copairing of morphisms: universal property of coproducts/pushouts.

To implement for coproducts of type T, define the method universal(::BinaryCoproduct{T}, ::Cospan{T}) and/or universal(::Coproduct{T}, ::Multicospan{T}) and similarly for pushouts.

Coproduct of objects.

To implement for a type T, define the method colimit(::ObjectPair{T}) and/or colimit(::DiscreteDiagram{T}).

Unique morphism out of an initial object.

To implement for a type T, define the method universal(::Initial{T}, ::SMulticospan{0,T}).

Unique morphism into a terminal object.

To implement for a type T, define the method universal(::Terminal{T}, ::SMultispan{0,T}).

Equalizer of morphisms with common domain and codomain.

To implement for a type T, define the method limit(::ParallelPair{T}) and/or limit(::ParallelMorphisms{T}).

Factor morphism through (co)equalizer, via the universal property.

To implement for equalizers of type T, define the method universal(::Equalizer{T}, ::SMultispan{1,T}). For coequalizers of type T, define the method universal(::Coequalizer{T}, ::SMulticospan{1,T}).

Initial object.

To implement for a type T, define the method colimit(::EmptyDiagram{T}).

Pairing of morphisms: universal property of products/pullbacks.

To implement for products of type T, define the method universal(::BinaryProduct{T}, ::Span{T}) and/or universal(::Product{T}, ::Multispan{T}) and similarly for pullbacks.

Product of objects.

To implement for a type T, define the method limit(::ObjectPair{T}) and/or limit(::DiscreteDiagram{T}).

Terminal object.

To implement for a type T, define the method limit(::EmptyDiagram{T}).

The category of finite sets and functions, and its skeleton.

Function out of a finite set.

This class of functions is convenient because it is exactly the class that can be represented explicitly by a vector of values from the codomain.

Function between finite sets.

The function can be defined implicitly by an arbitrary Julia function, in which case it is evaluated lazily, or explictly by a vector of integers. In the vector representation, the function (1↦1, 2↦3, 3↦2, 4↦3), for example, is represented by the vector [1,3,2,3].

This type is mildly generalized by FinDomFunction.

Finite set.

This generic type encompasses the category FinSet of finite sets and functions, through types FinSet{S} where S <: AbstractSet, as well as the skeleton of this category, through the type FinSet{Int}. In the latter case, the object FinSet(n) represents the set ${1,...,n}$.

Hash join algorithm.

Algorithm for limit of spans or multispans out of finite sets.

In the context of relational databases, such limits are joins.

Nested-loop join algorithm.

This is the naive algorithm for computing joins.

Meta-algorithm for joins that attempts to pick an appropriate algorithm.

Sort-merge join algorithm.

Force evaluation of lazy function or relation.

Whether the given function is indexed, i.e., supports efficient preimages.

The preimage (inverse image) of the value y in the codomain.

The category of finite sets and relations, and its skeleton.

The rig of booleans.

This struct is needed because in base Julia, the product of booleans is another boolean, but the sum of booleans is coerced to an integer: true + true == 2.

Object in the category of finite sets and relations.

See also: FinSet.

Binary relation between finite sets.

A morphism in the category of finite sets and relations. The relation can be represented implicitly by an arbitrary Julia function mapping pairs of elements to booleans or explicitly by a matrix (dense or sparse) taking values in the rig of booleans (BoolRig).

Relation in FinRel defined by a callable Julia object.

Relation in FinRel represented by a boolean matrix.

Boolean matrices are also known as logical matrices or relation matrices.

Categories of C-sets and attributed C-sets.

Transformation between attributed C-sets.

A morphism of C-sets is a natural transformation: a transformation between functors C -> Set satisfying the naturality axiom for all morphisms in C. This struct records the data of a transformation; it does not enforce naturality.

The transformation has a component for every object in C. When C-sets have attributes, the data types are assumed to be fixed. Thus, the naturality axiom for data attributes is a commutative triangle, rather than a commutative square.

Serialize an ACSet object to a JSON string

Is the transformation between C-sets a natural transformation?

Uses the fact that to check whether a transformation is natural, it suffices to check the naturality equation on a generating set of morphisms.

Pullback functorial data migration from one ACSet to another.

Note that this operation is contravariant: the data is transferred from X to Y but the functor, represented by two dictionaries, maps the schema for Y to the schema for X.

When the functor is the identity, this function is equivalent to copy_parts!.

Deserialize a dictionary from a parsed JSON string to an object of the given ACSet type

Deserialize a JSON string to an object of the given ACSet type

Read a JSON file to an object of the given ACSet type

Serialize an ACSet object to a JSON file

Structured cospans.

This module provides a generic interface for structured cospans with a concrete implementation for attributed C-sets.

Structured cospan.

The first type parameter L encodes a functor L: A → X from the base category A, often FinSet, to a category X with "extra structure." An L-structured cospan is then a cospan in X whose feet are images under L of objects in A. The category X is assumed to have pushouts.

Structured cospans form a double category with no further assumptions on the functor L. To obtain a symmetric monoidal double category, L must preserve finite coproducts. In practice, L usually has a right adjoint R: X → A, which implies that L preserves all finite colimits. It also allows structured cospans to be constructed more conveniently from an object x in X plus a cospan in A with apex R(x).

See also: StructuredMulticospan.

Construct structured cospan in R-form.

Construct structured cospan in L-form.

Object in the category of L-structured cospans.

Structured multicospan.

A structured multicospan is like a structured cospan except that it may have a number of legs different than two.

See also: StructuredCospan.

Construct structured multicospan in R-form.

Create types for open attributed C-sets from an attributed C-set type.

The resulting types, for objects and morphisms, each have the same type parameters for data types as the original type.

See also: OpenCSetTypes.

Create types for open C-sets from a C-set type.

Returns two types, for objects, a subtype of StructuredCospanOb, and for morphisms, a subtype of StructuredMulticospan.

See also: OpenACSetTypes.