TransWikia.com

A monad is just a monoid in the category of endofunctors, what's the enlightenment?

Computer Science Asked on November 30, 2021

Pardon the word play. I’m a little confused about the implication of the claim and hence the question.

Background: I ventured into Category Theory to understand the theoretical underpinnings of various categorical constructs and their relevance to functional programming (FP). It seems (to me) that one of the "crowning gems" at the intersection of Cat and FP is this statement:

A monad is just a monoid in the category of endofunctors

What is the big deal about this observation and what are its programmatic/design implications? Sources like sigfpe and many texts on FP seem to imply the mindblowingness of this concept but perhaps I’m unable to see the subtlety that’s being alluded to.

Here’s how I understand it:

Knowing something is a monoid allows us to extrapolate the fact that we can work within a map-reduce setting where the associativity of the operations allows us to split/combine the computation in arbitrary order i.e., (a1+a2)+a3 == a1+(a2+a3). It can also allow one to distribute this across machines and achieve high parallelization. (Thus, I could mentally go from a theoretical construct -> computer science understanding -> practical problem solving.)

For me it was obvious (as a result of studying Cat) to see that monads have a monoidal structure in the category of endofunctors. However, what is the implication one can draw from this and what is its programmatic/design/engineering impact when we’re coding with such a mental model?

Here’s my interpretation:

  • Theoretical Implication: All computable problems at their heart are monoidal in a sense.
    • Is this correct? If so, I can understand the enlightenment. It’s a different perspective on understanding the notion/structure of computable problems that wouldn’t be obvious if coming from only a Turing/Lambda model of computation and I can be at peace.
    • Is there more to it?
  • Practical Implication: Is it simply to provide a case for the do-notation style of programming? That is, if things are monoidal we can better appreciate the existence of the do/for constructs in Haskell/Scala. Is that it? Even if we didn’t know about the monoidal underpinnings, we needn’t invoke the monoidalness to make this claim since bind >>= and flatMap constructs are defined to be associative. So what gives? Or is it more to do with the foldability of monadic constructs and that is the indirect enlightenment that is being alluded to?

Question(s): What am I missing here? Is it simply the recognition of the fact that monads are generalized monoids and that they can be combined in any order similar to map-reduce operations like monoids? How does knowing about the monoidal property help improve the code/design in any way? What’s a good example of before/after to show this difference (before knowing about monads/monoidality and after)?

One Answer

This answer may not be exactly what you are looking for. That is, I think perhaps the importance of this characterisation is being overemphasised here. The quote

a monad in X is just a monoid in the category of endofunctors of X

is originally from Mac Lane's Categories for the Working Mathematician, where it appears as a helpful intuition for the definition of monad, which, alone, can seem quite unfamiliar at first. By characterising it as a monoid in a particular monoidal category, the reader is given an alternative perspective. Note that the chapter on monads actually comes before the chapter on monoidal categories: the remark is intended to be helpful, rather than precise (it is made precise only later).

The quote was then rephrased in James Iry's infamous article Brief, Incomplete and Mostly Wrong History of Programming Languages.

A monad is just a monoid in the category of endofunctors, what's the problem?

Presented out of context, as it is in the article, it is meant to amuse. The quote has since become a meme in the functional programming community, primarily because it is amusing, rather than a key insight for functional programming (though it does also serve to pique the curiosity of functional programmers, drawing them into the wonderful world of category theory). My view is that this characterisation, while helpful and interesting, is not as important as one might imagine from its popularity.

However, this is not to say there is no insight to be gained from this characterisation. First, let me point out that, while the presentation of a monad with a multiplication and unit is clearly suggestive of a monoid, as you point out, the Kleisli presentation, with a bind and return operation, is not. It is the Kleisli presentation that is common in functional programming, so certainly the characterisation as a monoid is more interesting from this perspective.

From a theoretical perspective, one of the insights is indeed that many natural structures in computer science (and mathematics) are monoidal. From the perspective of monads (particularly with their relation to cartesian operads and Lawvere theories), monoidal structure corresponds to substitution structure (equivalently, composition structure). Substitution is ubiquitous in computer science (for example, capture-avoiding substitution in a type theory, or grafting of trees). Monads are just one more example.

While understanding formally the statement in question may not be enlightening, I suggest that it is enlightening to understand the different perspectives on monads, as it allows you to see the different ways in which monads might be used (e.g. as containers, describing algebraic structure, describing multi-compositional systems, etc.). It can be hard to appreciate just how often they pop up without having seen the different lights in which they can be seen. In this sense, monads as monoids is just one perspective (and probably not the most enlightening).

Finally, while monads themselves are inarguably very useful in pure functional programming generally, I'm not sure the perspective as monads as monoids is helpful per se. I think the Kleisli perspective, which happens to be equivalent, is the most enlightening perspective here.

In summary, this response may be a little disappointing: I don't think that understanding this relationship is all that helpful or enlightening practically (i.e. for programming). However, it is a useful perspective to keep in mind, along with the others, when considering monads theoretically.

Answered by varkor on November 30, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP