Branching behavior in string diagrams/monoidal categories?

Question

I am currently working through Peter Selinger's paper "Towards a Quantum Programming Language", and trying to connect it with what I already know about monoidal categories and string diagrams.

However, his flow charts involve branching behavior for measurements, and I don't know how to tie that to the categorical machinery.

More specifically, how could I take the following specification and represent it in a monoidal category? What additional structure do I need?

f: Int -> Int

f(x) = if {x > 10}
       then x+3
       else 0

My best guess would be to require coproducts, as that is how I would approach the problem in a Cartesian context.

Answer 1

You can represent such a branching behaviour in bimonoidal categories (also known as rig categories).

In addition to your multiplicative monoidal structure $\otimes$, which is used to represent compound systems, you need another monoidal structure $\oplus$ to model the branching histories. A category is bimonoidal when it has these two structures and $\otimes$ distributes over $\oplus$.

Let us consider a slight variation on your example specification to illustrate that:

f(x,y) = if (x > 10)
         then x + 3
         else y + 3

You can model it like this:

• $a : \text{Int} \rightarrow \text{Int} \oplus \text{Int}$ is the map that sends its input to the first component if it is greater than 10, and to the second component otherwise
• $b : \text{Int} \rightarrow \text{Int}$ is the morphism that adds 3 to its argument
• $c : \text{Int} \rightarrow I$ is the discarding map, where $I$ is the monoidal unit for $\otimes$.
• $d : \text{Int} \oplus \text{Int} \rightarrow \text{Int}$ is the codiagonal map (mapping both sides of the sum to the same object).

Then your algorithm can be represented as $d \circ ((b \otimes c) \oplus (c \otimes b)) \circ (a \otimes 1_{\text{Int}})$. You can represent it graphically using sheet diagrams for bimonoidal categories, which generalize string diagrams for monoidal categories:

Manipulate diagram interactively

(The reason why I tweaked your example a bit is to demonstrate how the multiplicative monoidal structure can be used in these diagrams. Your example only had a single variable so it could be represented with the additive monoidal structure only, so with regular string diagrams for that monoidal structure.)