Operad Algebra

definition theorem example

An algebra for an Operad $\mathcal{O}$ is an operad functor $F:\mathcal{O}\to \mathbf{Set}$: it assigns to each type $t$ a set $F(t)$ of fillers for boxes of type $t$, and to each operation (wiring diagram) $f\in \mathcal{O}(t_1,\dots ,t_n;t)$ a function $F(f):F(t_1)\times \cdots \times F(t_n)\to F(t)$ that assembles $n$ fillers into one — e.g. “takes $n$ circuits with interfaces $t_1,\dots ,t_n$ and returns a circuit with boundary $t$“. Just as set-valued functors $\mathcal{C}\to \mathbf{Set}$ are database instances, set-valued operad functors are the applications obeying a compositional grammar.

Sources: 7 Sketches §6.5.3 (Definition 6.99, Example 6.100, Proposition 6.101), Remark 5.74 (algebraic theories), §6.6; Catlab oapply; CTfS Definition 5.4.1.8, Application 5.4.2.2, Example 5.4.2.6, Application 5.4.2.7

Example 6.100 (circuits). $\mathbf{Circ}:\mathbf{Cospan}\to \mathbf{Set}$ sends $t\in \mathbb{N}$ to the set of circuits with $t$ marked terminals; a wiring diagram $\phi \in \mathbf{Cospan}(2,2,2;0)$ gives $\mathbf{Circ}(\phi ):\mathbf{Circ}(2{)}^3\to \mathbf{Circ}(0)$, which applied to a battery, a switch and a lamp-with-resistor yields the closed light-switch circuit of §6.1. This is the decorated-cospan story in operadic form.

Subsets as an algebra (CTfS Example 5.4.2.6, Application 5.4.2.7). On the operad of relations, $S(x)=\mathcal{P}(x)$ is an algebra: given a relation $R\subseteq {\prod }_i{x}_i\times y$ and subsets $x_i^{\prime }\subseteq x_i$, take the image in $y$ of the tuples of $R$ whose inputs lie in the $x_i^{\prime }$. Read as survival: the super-entity survives exactly the phenomena that translate into phenomena every sub-entity survives. Materials and their strengths are two algebras on one operad, and a morphism of algebras relates them (Operad).

Proposition 6.101. $\mathbf{Cospan}$-algebras are equivalent to hypergraph props — so $\mathbf{Cospan}$ is “the theory of hypergraph categories” (cf. Theorem 6.58). Advantages of the operadic view: every hypergraph prop arises (decorated cospans give only some), and one may vary the operad ($\mathbf{Cospan}$ → cobordisms → wiring diagrams without passing wires) to get different compositionality rules. Compare: monoid objects are algebras of the prop “theory of monoids” (Remark 5.74); Catlab’s oapply(diagram, fillers) evaluates an operad algebra — for finite relations, Petri nets, dynamical systems, or circuits — on an Undirected Wiring Diagram.

JuliaHaskell

Docs: FinSets · Free diagrams · Relational programs / UWDs

using Catlab, Catlab.WiringDiagrams, Catlab.Programs
# the operad algebra of relations on UWDs: a filler is a relation R ⊆ A × B, stored as a span
# A ← R → B of finite sets, and oapply glues fillers along the diagram (a limit = a join of tables)
uwd = @relation (x, z) begin
  R(x, y); S(y, z)
end
relspan(pairs, A, B) = Span(FinFunction(first.(pairs), A), FinFunction(last.(pairs), B))
R = relspan([(1, 1), (1, 2), (2, 2)], 2, 2)        # ≤ on {1, 2}
S = relspan([(1, 2), (2, 1)], 2, 2)                # swap
RS = oapply(uwd, [R, S])                           # the composite relation R ; S, as a span
πx, πz = legs(RS)
sort([(πx(i), πz(i)) for i in apex(RS)])           # [(1, 1), (1, 2), (2, 1)]
# oapply works the same way for open Petri nets (AlgebraicPetri) and other hypergraph categories

-- an algebra assigns filler sets to types and an assembly function to each wiring diagram (schematic)
class Operad op => Algebra op a where
  assemble :: op -> [a] -> a       -- F(f)(fillers)