A tour of String Diagrams and Monoidal Categories

This post is the written version of a talk that I gave at Scale by the Bay 2020. The slides and the recording are also available. The code now uses the current Scala 3 syntax.

Scala version used: 3.9.0 (ZIO 1.0.18 for the interpreter)
Latest revision: Sep 23, 2026

Goals

• Show why Monoidal Categories are a good modeling tool for a certain class of domains
• Show how Monoidal Categories can be represented graphically via String Diagrams

The references are at the end of the post.

Part I: String Diagrams as Processes

Processes

Processes are everywhere in computing and mathematics:

• Functions: sort: List[A] => List[A]
• Mathematical functions: $f(x, y) = x^2 + y^2$
• Matrices: $M = \begin{pmatrix} a & b & c \\ d & e & f \end{pmatrix}$
• Real-world processes: Recipes (ingredients → dish), hardware connections (USB cord connecting a microphone to a computer)

A Process

A process can be visualized as a box with input and output wires:

The process p takes an input of type A and produces outputs of types B and C.

Processes as Diagrams

We can represent different kinds of processes as string diagrams:

Sorting function:

Mathematical function $x^2 + y^2$:

Cooking process:

Matrix (3 columns → 2 rows):

Parallel Composition

Two processes can be composed in parallel using the tensor product $\otimes$:

Sequential Composition

Processes can be composed sequentially using >>>:

Complex Diagrams

Complex diagrams can be built by combining parallel and sequential composition:

Process Theories

A "process theory" is an interpretation of a diagram in terms of a concrete class of processes.

In particular it provides an interpretation of wires, boxes, and composition operations of diagrams.

Examples of process theories:

• Functions and sets
• Linear maps and vector spaces
• Matrices and natural numbers

Diagram Equations

Diagrams satisfy certain equations. For example, boxes can slide along wires:

Boxes can also move through a crossing of wires. (This uses the swap of symmetric monoidal categories, from Part II.)

This is a general principle, a theorem of Joyal and Street: if you can deform one diagram into another in the plane, without cutting wires, and the inputs stay on the left and the outputs on the right, then both diagrams denote the same process. In a symmetric monoidal category, wires can also pass through each other, as in the second example.

Process Equations

Processes can satisfy domain-specific equations:

Idempotence of sort:

Identity element for addition:

Part II: String Diagrams as Monoidal Categories

Formalization

This diagrammatic language can be formalized by using category theory, specifically monoidal categories.

Plan

1. Categories

A category consists of:

• Objects: A, B, C, D, ...
• Arrows (morphisms) between objects: $f: A \to B$
• Composition: if $f: A \to B$ and $g: B \to C$, then $g \circ f: A \to C$
• Identity: for each object A, an identity morphism $1_A: A \to A$

As string diagrams:

A morphism $f: A \to B$:

The identity $1_A$:

Composition $g \circ f$. Diagrams read from left to right, so they write it as $f \mathbin{>\!\!>\!\!>} g$ ("$f$, and then $g$"):

Category Equations

Left identity: $1_B \circ f = f$

Right identity: $f \circ 1_A = f$

Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$

Example: Matrices

Matrices (for example, with real entries) form a category where:

• Objects: natural numbers (representing dimensions)
• Arrows $n \to m$: matrices of size $m \times n$
• Composition: matrix multiplication
• Identity $1_n$: identity matrix $I_n$

For a matrix $A$ with $n$ columns and $m$ rows:

$A = \begin{pmatrix} a_{11} & \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{m1} & \cdots & a_{mn} \end{pmatrix}$

Matrix multiplication $A \cdot B$ applies $B$ first, so its diagram is $B \mathbin{>\!\!>\!\!>} A$:

Identity matrix:

$I_n = \begin{pmatrix} 1 & \cdots & 0 \\ \vdots & \ddots & \vdots \\ 0 & \cdots & 1 \end{pmatrix}$

2a. Strict Monoidal Categories

A strict monoidal category is a category with a monoid structure on the objects and arrows.

This means we have a parallel composition operation: an associative binary operation called the tensor product:

$\otimes : \mathcal{C} \times \mathcal{C} \to \mathcal{C}$

On objects:

On arrows:

Unit object:

There is a neutral or unit object $I$, with identity $1_I: I \to I$. It is drawn as the empty diagram, so a tensor with $I$ changes nothing:

For example, a morphism $f: I \to B$ (from the unit) is a box with no input wire:

One More Law

The tensor product and composition satisfy an interchange law:

$(f_1 \mathbin{>\!\!>\!\!>} g_1) \otimes (f_2 \mathbin{>\!\!>\!\!>} g_2) = (f_1 \otimes f_2) \mathbin{>\!\!>\!\!>} (g_1 \otimes g_2)$

This says that it doesn't matter whether we first compose sequentially then in parallel, or first in parallel then sequentially:

Together with $1_A \otimes 1_B = 1_{A \otimes B}$, this law says that $\otimes$ is a functor from $\mathcal{C} \times \mathcal{C}$ to $\mathcal{C}$.

Matrices Again

Matrices form a monoidal category using the Kronecker product as parallel composition:

$A \otimes B = \begin{pmatrix} a_{11}B & \cdots & a_{1n}B \\ \vdots & \ddots & \vdots \\ a_{m1}B & \cdots & a_{mn}B \end{pmatrix}$

• On objects it operates as multiplication of natural numbers: if $A$ is $m \times n$ and $B$ is $p \times q$, then $A \otimes B$ is $mp \times nq$
• The number 1 is the unit $I$: a $1 \times 1$ matrix $(c)$ is a scalar, and $(c) \otimes B = cB$

(The direct sum $A \oplus B$, the block-diagonal matrix, gives another monoidal structure on matrices. It adds the objects, and its unit is 0.)

2b. Monoidal Categories

In many cases it's not literally true that:

$(X \otimes Y) \otimes Z = X \otimes (Y \otimes Z)$

or

$I \otimes X = X = X \otimes I$

For example, in Scala the types ((A, B), C) and (A, (B, C)) are different, and so are (A, EmptyTuple) and A. They are only isomorphic: functions convert between them in both directions without loss.

Instead we're forced to require natural isomorphisms (natural means that they commute with the arrows):

• Associator: $\alpha_{X,Y,Z} : (X \otimes Y) \otimes Z \xrightarrow{\sim} X \otimes (Y \otimes Z)$
• Left unitor: $\lambda_X : I \otimes X \xrightarrow{\sim} X$
• Right unitor: $\rho_X : X \otimes I \xrightarrow{\sim} X$

These must satisfy certain coherence laws: the pentagon and triangle equations (see the monoidal laws in Part III).

3. Cartesian Monoidal Categories

A Cartesian monoidal category has additional structure:

Projections - we can extract the first and second components:

Diagonal - we can duplicate information:

Terminal morphism - we can discard information:

These operations satisfy laws. For example, to duplicate a value and then take the first (or the second) copy gives back the value: Δ >>> fst = id. Also, ! is the only arrow from A to $I$: the unit is a terminal object, and $\otimes$ is the categorical product.

4. Symmetric Monoidal Categories

A symmetric monoidal category has a swap operation. (Every Cartesian monoidal category is symmetric: its swap takes the second and then the first component, snd &&& fst in the DSL of Part III. The plan adds the operations one at a time.)

With inverse:

This representation is chosen so that:

Furthermore, the swap satisfies symmetry: the swap of $X$ and $Y$ is the inverse swap of $Y$ and $X$,

that is, two swaps in a row give back the original wires:

Circuit Diagrams

The diagrams we have discussed so far contain no loops. To be more precise, they are called circuit diagrams.

Feedback loops need more structure: a trace, as in traced monoidal categories. Compact closed categories are an important example (they won't be discussed here).

Part III: String Diagrams in Scala

Airflow-like Process Manager

We can express complex process pipelines using a DSL. Given the boxes of the diagram, with their input and output types, the program composes them:

// The boxes of the diagram
def p1: A ~> C
def p2: (A, C) ~> D
def p3: D ~> (F, G)
def p4: F ~> H
def p5: A ~> J
def p6: J ~> K
def t: (H, K) ~> B

val initial: A ~> ((A, A), A) =
  Δ[A] >>> (id[A] ++ Δ[A]) >>> assocL

val top: (A, A) ~> H =
  (id[A] ++ p1) >>> p2 >>> p3 >>> fst >>> p4

val bottom: A ~> K =
  p5 >>> p6

val program: A ~> B =
  initial >>> (top ++ bottom) >>> t

This corresponds to the complex diagram:

initial makes three copies of the input: top uses the first two, and bottom uses the third. The operations ~>, >>>, ++, Δ and assocL come from the DSL of the next section.

Tagless Process DSL

We can define a tagless final DSL for processes. A ~> B is a process from A to B, and B <~ A is the same type, written from right to left.

Category Structure

import scala.annotation.targetName

trait ProcessDSLOps[Process[_, _]] {
  type ~>[A, B] = Process[A, B]
  type <~[B, A] = Process[A, B]

  def id[A]: A ~> A

  extension [A, B, C](f: A ~> B)
    @targetName("andThen")
    def >>>(g: B ~> C): A ~> C

  extension [A, B, C](g: B ~> C)
    @targetName("compose")
    def ◦(f: A ~> B): A ~> C = f >>> g

The trait continues in the next two blocks.

Cartesian Structure

  def fst[A, B]: (A, B) ~> A
  def snd[A, B]: (A, B) ~> B

  extension [A, B, C](f: A ~> B)
    @targetName("mergeInput")
    def &&&(g: A ~> C): A ~> (B, C)

  @targetName("duplicate")
  def Δ[A]: A ~> (A, A) = id[A] &&& id[A]

  // terminal object and monoidal unit
  type I = EmptyTuple

  def discard[A]: A ~> I

Monoidal Structure

  def assocR[X, Y, Z]: ((X, Y), Z) ~> (X, (Y, Z))
  def assocL[X, Y, Z]: ((X, Y), Z) <~ (X, (Y, Z))

  def injR[X]: X ~> (I, X)
  def injL[X]: X ~> (X, I)

  // tensor on objects: A ⊗ B = (A, B)
  // tensor on arrows: f ⊗ g = f ++ g
  extension [A1, A2, B1, B2](f: A1 ~> B1)
    @targetName("combine")
    def ++(g: A2 ~> B2): (A1, A2) ~> (B1, B2)

  def swap[X, Y]: (X, Y) ~> (Y, X)
  def swapInverse[X, Y]: (X, Y) <~ (Y, X)
}

Laws

The DSL must satisfy the laws of a symmetric monoidal category. Each law gives two processes that must be equal, lhs <-> rhs. A test can check them for a concrete interpreter, for example on sample inputs:

class Law extends scala.annotation.StaticAnnotation

final case class IsEq[A](lhs: A, rhs: A)

trait ProcessDSLLaws[Process[_, _]] extends ProcessDSLOps[Process]:
  // Both sides must be processes of the same type
  extension [A, B](lhs: A ~> B) def <->(rhs: A ~> B): IsEq[A ~> B] = IsEq(lhs, rhs)

The laws below are members of this trait, so they can use the operations of the DSL. Because <-> requires the same type on both sides, the compiler rejects a law whose sides do not match.

Category Laws

@Law
def associativity[A, B, C, D](
  f: A ~> B,
  g: B ~> C,
  h: C ~> D
) =
  h ◦ (g ◦ f) <-> (h ◦ g) ◦ f

@Law
def identityL[A, B](f: A ~> B) =
  (id[B] ◦ f) <-> f

@Law
def identityR[A, B](f: A ~> B) =
  f ◦ id[A] <-> f

Tensor Laws

@Law
def tensorCompositionLaw[A1, A2, B1, B2, C1, C2](
  f1: A1 ~> B1, f2: A2 ~> B2,
  g1: B1 ~> C1, g2: B2 ~> C2,
) =
  (g1 ◦ f1) ++ (g2 ◦ f2) <-> (g1 ++ g2) ◦ (f1 ++ f2)

@Law
def tensorIdentityLaw[A, B] =
  id[A] ++ id[B] <-> id[(A, B)]

Monoidal Laws

Here fst[X, I] and snd[I, Y] act as the right and the left unitor.

@Law
def triangleEquation[X, Y] =
  assocR[X, I, Y] >>> (id[X] ++ snd[I, Y]) <->
  (fst[X, I] ++ id[Y])

@Law
def pentagonEquation[W, X, Y, Z] =
  (assocR[W, X, Y] ++ id[Z]) >>>
  assocR[W, (X, Y), Z] >>>
  (id[W] ++ assocR[X, Y, Z]) <->
  (assocR[(W, X), Y, Z] >>> assocR[W, X, (Y, Z)])

Symmetric Monoidal Laws

@Law
def hexagonEquation1[X, Y, Z] =
  (assocL[X, Y, Z] >>> (swap[X, Y] ++ id[Z]) >>>
  assocR[Y, X, Z] >>> (id[Y] ++ swap[X, Z]) >>>
  assocL[Y, Z, X]) <->
  swap[X, (Y, Z)]

@Law
def symmetry[X, Y] =
  swap[X, Y] <-> swapInverse[Y, X]

The slides also show a second hexagon equation. In a symmetric monoidal category, it follows from the first one and from symmetry.

ZIO Interpreter

We can interpret processes as ZIO effects. RIO[A, B] is an effect that needs an input of type A, and gives a B or fails: roughly, RIO[A, B] ≈ A => Either[Throwable, B]. The interpreter uses ZIO 1, because ZIO 2 removed the operations that use the environment as the input, such as RIO.first and RIO.swap.

import scala.annotation.targetName
import zio.RIO

given RIOProcessOps: ProcessDSLOps[RIO] with
  def id[A] = RIO.identity[A]

  extension [A, B, C](f: RIO[A, B])
    @targetName("andThen")
    def >>>(g: RIO[B, C]): RIO[A, C] = f andThen g

  def fst[A, B]: RIO[(A, B), A] = RIO.first
  def snd[A, B]: RIO[(A, B), B] = RIO.second

  extension [A, B, C](f: RIO[A, B])
    @targetName("mergeInput")
    def &&&(g: RIO[A, C]): RIO[A, (B, C)] = f &&& g

  def discard[A]: RIO[A, I] = RIO.succeed(EmptyTuple)

  def assocR[X, Y, Z]: ((X, Y), Z) ~> (X, (Y, Z)) =
    RIO.fromFunction { case ((x, y), z) => (x, (y, z)) }
  def assocL[X, Y, Z]: ((X, Y), Z) <~ (X, (Y, Z)) =
    RIO.fromFunction { case (x, (y, z)) => ((x, y), z) }

  def injR[X]: X ~> (I, X) = RIO.fromFunction(a => (EmptyTuple, a))
  def injL[X]: X ~> (X, I) = RIO.fromFunction(a => (a, EmptyTuple))

  extension [A1, A2, B1, B2](f: A1 ~> B1)
    @targetName("combine")
    def ++(g: A2 ~> B2): (A1, A2) ~> (B1, B2) =
      val left = fst[A1, A2] >>> f
      val right = snd[A1, A2] >>> g
      left.zipWithPar(right)((x, y) => (x, y))

  def swap[X, Y]: (X, Y) ~> (Y, X) = RIO.swap
  def swapInverse[X, Y]: (X, Y) <~ (Y, X) = RIO.swap

Inside the instance, f andThen g, f &&& g and fst[A1, A2] >>> f call the methods of ZIO itself, because a method of a class has priority over an extension method.

Process DSL Architecture

The DSL is designed with multiple interpreters:

Category of Port Graphs

Port graphs provide a concrete representation for string diagrams. (The PortGraph type and its operations are not shown here.)

val graph1 =
  PortGraph(
    boxes = SeqMap(
      a -> (List("A"), List("B","C","D")),
      b -> (List("D","C","G"), List("Y","E","F")),
      c -> (List("B","Y"), List("Z")),
    ),
    incoming = List((a, 0), (b, 2)),
    inner = List(
      (a, 0) -> (c, 0),
      (a, 1) -> (b, 1),
      (a, 2) -> (b, 0),
      (b, 0) -> (c, 1),
    ),
    outgoing = List((c, 0), (b, 1), (b, 2))
  )

val graph2 = singleBox("x", List("Z", "E", "F"), List("W"))

val combined = graph1 andThen graph2

def render[B, P](pg: PortGraph[B, P]): graphviz.model.Graph = ???

The identity port graph passes each wire straight through:

Because the DSL is tagless, one program has several interpretations:

1. As a port graph, we can compose it sequentially and in parallel, and render it with Graphviz or D3.
2. With the ZIO interpreter, we can run it.

References

• Brendan Fong, David I. Spivak. An Invitation to Applied Category Theory: Seven Sketches in Compositionality. Cambridge University Press, 2019.
• John C. Baez, Mike Stay. Physics, Topology, Logic and Computation: A Rosetta Stone. 2009.
• Bob Coecke, Aleks Kissinger. Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning. Cambridge University Press, 2017.
• Aleks Kissinger. Pictures of Processes: Automated Graph Rewriting for Monoidal Categories and Applications to Quantum Computing. DPhil thesis, University of Oxford, 2011.
• André Joyal, Ross Street. The Geometry of Tensor Calculus, I. Advances in Mathematics, 1991.