Monads are Dominoes

by

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

such that

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.

Associativity:

Identity:

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:

x

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  .

Proof:

Associativity:

Identity:

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?

7 thoughts on “Monads are Dominoes”

  1. Some questions:
    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?)

    Reply

    • 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 s and D (D s) is D eta. In general, the morphism between D a and D b for any function f: a -> b is D f.

      Reply

      • “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 eta of type a -> D a takes any value v in a to the domino (v, v) in D a.

      • 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.

Leave a comment