It’s about time I made my contribution to the zoo of monad tutorials. After explaining the concept of monads to somebody who is not a programmer or a mathematician, I was told that what I had explained sounded exactly like a game of dominoes.
However, instead of explaining monads in terms of a cute metaphor about dominoes, I’m just going to throw you into the deep end. Deep breath!
Definition: A category is given by objects and arrows between these objects. Each arrow has a unique source object and a target object . For every three objects , , and , and arrows and , there is a composite arrow
Composition is associative: if , , and , then
There exists a unique identity arrow for each object For every object , there exists an arrow such that for every arrow , we have
A category for dominoes:
The objects of the category are the natural numbers. An arrow in the category is a domino piece with two numbers on it: . A composition of arrows is two domino pieces placed together end-to-end by the following equation:
The identity arrow for each object is a domino piece with the same number on both ends.
A monad for dominoes
Definition: A monad is given by a functor (from a category to itself, i.e. an endofunctor in ), equipped with natural transformations:
where is the identity functor and x is functor composition. This must satisfy the axioms that and are identity transformations, and (i.e. is associative).
The dominoes need not be annotated with numbers, but might be annotated with any set of objects. Therefore, there exists an endofunctor on the category of sets, such that for all sets , we can construct the set of dominoes .
For every object in , we can construct a domino . This is for our monad. Then, for the set of dominoes , we can construct which is the set of dominoes annotated with other dominoes. For any pair of dominoes in , composed end-to-end, we can see it as a single domino in . The operation in our monad is then the fact that for any such pair of dominoes , it behaves as the domino with regard to composition with other dominoes in .
Exercises left to the reader:
1. What does a monoid in the category of dominoes look like?
2. How would the game of dominoes change if it allowed products and coproducts?
3. Can you come up with a coherent theory describing the behavior of “spinners” in the game of dominoes?
1. From your explanation, isn’t D a functor from Set to Domino? So it is not an endofunctor?
2. The domino category is first defined as natural numbers as objects and (a,b) as arrows. Then eta maps an object in S to (s,s)? So now the objects are pairs? What are the arrows? Isn’t eta supposed to be a natural transformation from 1 to D?
3. D(D(S)) is dominos annotated with other dominos. Then what are the morphisms between regular dominos and dominos annotated with other dominos? (maybe there aren’t any?)
1. It is an endofunctor in Set. In the latter half, we’re considering dominoes on any sets, not just the numbers. In this version of the game, we still want the types on the ends to match, so it’s necessary that the type (a,b) is identical to the type (b, a), otherwise the unit doesn’t hold.
2. Now the objects are sets instead of numbers, including the sets of dominoes. The arrows are now ordinary functions. Yes, T in the definition is D in the example.
3. The morphism between
D (D s)is
D eta. In general, the morphism between
D bfor any function
f: a -> bis
“For every object s in S , we can construct a domino (s,s). This is eta for our monad. “. What do you mean by ‘(s,s)’ it doesn’t look like a set, so is it a morphism? But eta is supposed to be a natural transformation mapping 1 to D. So shouldn’t it show how s is mapped to D(s) so that for f: s1 -> s2, eta(f(s1)) = D(f)(eta(s1)) ?
Ittay: The morphism
a -> D atakes any value
ato the domino
In the monad we’re actually cheating the game a bit, because ((1, 2), (1, 2)) is not a valid line of play. However, ((1, 2), (2, 1)) is perfectly valid, but that becomes (1, 1) by the mu operation we’ve defined, which isn’t an identity. So really, we have to consider (1, 2) and (2, 1) to be not identical but isomorphic, which requires us to consider “arrows between arrows” in a very specific way. So composition of dominoes really only forms a monad when considered on a bicategory as follows:
* The 0-cells are numbers. The 1-cells are lines of dominoes. The 2-cells are morphisms between such lines, and there exist isomorphisms between (x, y) and (y, x) for all 0-cells x and y.
* For every pair of numbers (x, y), there is a category D(x, y) of domino lines that start with x and end with y.
* For every three numbers (x, y, z), there is a bifunctor from D(x, y) * D(y, z) to D(x, z) describing the composition of such lines.
But, you know, close enough.
If eta transforms s of S to (s,s) in D(S), then D(S) is the set of pairs of the form (a,b), right? But dominoes started as “single” objects where the “domino” analogy was the arrow a -> b. If a domino is an object (a,b), then I don’t think it forms a category with the intuition of arrows as paths of dominoes since the paths (a,b) -> (b,c) and (b,c) -> (c,d) do not compose to a path (a,b) -> (c,d) (not a valid domino path). It could be a category if (a,b) are arrows a->b, but then I’m confused how it suddenly becomes a set of pairs.
But then according to your latest comment (1,2) and (2,1) are supposed to be isomorphic. So these are arrows then? I’m confused.
What do you mean, in category terminology, by “the 1 cells are lines of dominoes”? I thought the 1 cells are supposed to be the arrows of the category. And aren’t the 2-cells supposed to be the pairs (f,g) s.t. the codomain of f is the domain of g (composition)?
“D(S) is the set of pairs of the form (a,b), right?”
Not exactly. D(S) is the set of strings of dominoes. It doesn’t quite work out if we look at them as simply the pairs.
“But dominoes started as “single” objects where the “domino” analogy was the arrow a -> b. If a domino is an object (a,b)”
You should not think of the dominoes as the objects in the category. They are the arrows. The domino (x, y) is an arrow from x to y. The composition of the arrows (x, y) and (y, z) is an arrow from x to z.
“And aren’t the 2-cells supposed to be the pairs”
No, 2-cells are the morphisms between arrows.
Have a look at the category Rel of binary relations among sets. It’s essentially the same category as the one under discussion.