In Part 1, I explained how algebra can shed some light on a quite restricted class of react-apps. Today, I will lift one of the restrictions. This step needs a new kind of algebraic structure:
Category theory is a large branch of pure mathematics, with many facets and applications. Most of the latter are internal to pure mathematics. Since I have a very special application in mind, I will give you a definition which is less general than the most common ones.
Categories can be thought of as generalized monoids. At the same time, a Category is a labelled, directed multigraph with some extra structure. Here is a picture of a labelled directed multigraph – its nodes are labelled with upper case letters and its edges are labelled with lower case letters:
If such a graph happens to be a category, the nodes are called objects and the edges morphisms. The idea is, that the objects are changed or morphed into other objects by the morphisms. We will write for a morphism from object to object .
But I said something about extra structure and that categories generalize monoids. This extra structure is essentially a monoid structure on the morphisms of a category, except that there is a unit for each object called identity and the operation “” can only be applied to morphisms, if they form “a line”. For example, if we have morphisms like k and i in the picture below, in a category, there will be a new morphism ““:
Note that “” is on the right in “” but it is the first morphism if you follow the direction indicated by the arrows. This comes from function composition in mathematics, which suffers from the same weirdness by some historical accident. For now that just means that chains of morphisms have to be read from right to left to make sense of them.
For the indentities and the operation ““, we can ask for the same laws to hold as in a monoid, which will complete the definition of a category:
Definition (not as general as it could be…)
A category consists of the following data:
- A set of objects A,B,…
- A set of morphisms
- An operation “” which for all (consecutive) pairs of morphisms and returns a morphism
- For any object a morphism
Such that the following laws hold:
- “ ” is associative: For all morphisms , and , we have:
- The identities are left and right neutral: For all morphisms we have:
Before we go to our example of interest, let us look at some examples:
- Any monoid is a category with one object O and for each element m of the monoid a morphism . “” is defined to be .
- The graph below can be extended to a category by adding the morhpisms and an identity for and . The operation “” is defined as juxtaposition, where we treat the identities as empty sequences. So for example, is .
- More generally: Let be a labelled directed graph with edges and nodes . Then there is a category with objects and morphisms all sequences of consectutive edges – including the empty sequence for any node.
So let’s generalize Part 1 with our new tool. Our new scope are react-apps, which have actions without parameters, but now, action can not neccessarily be applied in any order. If an action can be fired, may now depend on the state of the app.
The smallest example I can think of, where we can see whats new, is an app with two states, let’s call them ON and OFF and two actions, let’s say SWITCH_ON and SWITCH_OFF:
Let us also say, that the action SWITCH_ON can only be fired in state OFF and SWITCH_OFF only in state ON. The category for that graph has as its morphims the possible sequences of actions. Now, if we follow the path of part 1, the obvious next step is to say that SWITCH_ON after SWITCH_OFF (and the other way around) is the same as the empty action-sequence — which leads us to…
We made a pretty hefty generalization from monoids to categories, but the theory for quotients remains essentially the same. As we defined equivalence relations on the elements of a monoid, we can define equivalence relations on the morphisms of a category. As last time, this is problematic in general, but turns out to just work if we replace sequences of morphisms in the action category with matching source and target.
So in the example above, it is ok to say that SWITCH_ON SWITCH_OFF is the empty sequence on ON and SWITCH_OFF SWITCH_ON is the empty sequence on OFF (keep in mind that the first action to be executed is on the right). Then any action sequence can be reduced to simply SWITCH_ON, SWITCH_OFF or an empty sequence (not the empty sequence, because we have two of them with different source and target). And in this case, the quotient category will be what we drew above, but as a category.
Of course, this is not an example where any high-powered math is needed to get any insights. So far, these posts where just about understanding how the math works. For the next part of this series, my plan is to show how existing tools can be used to calculate larger examples.