What isn’t a Monad

What isn’t a Monad

In this post: interesting examples of types that are almost monads.

Preface

This is another post where I talk about monads but avoid explicitly explaining what a monad is in much detail. That’s pretty well covered elsewhere. This post may or may not be helpful to you, if you don’t “get it” yet. But don’t worry, I promise to not contribute to the running joke of explaining the abstract by going more abstract!.

There are tons of types that are almost monads, but I’ve selected what I think are the best three (plus a trivial one). They each represent a common way to fail at being a monad. For each type, I’ve create a small graphic showing the type (to the right) as well as a similar type that is a monad (to the left).

Since a type being a monad just means it supports three operations (wrapping a value into the type, applying a transformation function to values “within” the type, and flattening the type when it ends up inside itself), the graphics are just representations of each operation. In each case the value-to-wrap will be represented as a puzzle piece, and the function applied when transforming will be IsEven.

Each monad and not a monad has been implemented in C#, and can be viewed on github should my explanation leave some detail ambiguous.

Not a Monad #1: Quantum Superpositions

Lets start with some nice simple quantum physics.

A quantum superposition is a lot like a probability distribution, except the probabilities are complex numbers. In other words, a superposition is just a collection of distinct values paired with complex numbers called amplitudes. The probability of observing a value is the squared length of its amplitude.

Probability distributions form a nice monad. Collections of things and pairings of things are often monads. So you might, by analogy, expect quantum superpositions to also form a monad. That would be true, if only interference didn’t exist.

A superposition can’t contain the same value twice. Neither can a probability distribution. When you have two equal values in a probability distribution, you really have a single value with a probability equal to the sum of the equal values’ probabilities. The same thing applies to superpositions, except you add (“interfere”) amplitudes instead of probabilities.

Unfortunately, adding amplitudes has a nasty tendency to violate the condition that things must add up to 100%. The following graphic contrasts that issue against the probability distribution monad, which works almost exactly the same way but doesn’t run into problems:

(Click for a larger version)

(Update: I improved the above graphic. Here’s the old version.)

The above graphic is showing that, although you can wrap values into a superposition, interference when transforming and flattening can violate conservation of total probability.

Notice how, in the graphic, applying an IsEven function to the values in a superposition of the numbers 1, 2, and 3 merges 1 and 3 into the same value (Odd). Because 1 and 3 point in opposite directions, merging them causes destructive interference and cancels out lots of probability (a proper quantum operation would have accompanying constructive interference to undo the loss).

The opposite problem, failing due to constructive interference, is shown in the graphic when flattening a superposition of superpositions. The unflattened superposition contains two superpositions, each of which is just 100% letter A (although with different phases). Flattening causes the two ways to get A to be added together, resulting in a more-than-100% chance of observing A (which I choose to interpret as causing the universe to smash into itself).

I find the fact that superpositions aren’t monads really interesting. Quantum physics is notoriously non-intuitive, so it’s somewhat… appropriate that superpositions aren’t monads. Types that are monads have nice properties that make them easy to use and understand, after all.

Not a Monad #2: Square Matrices

Next up, square matrices. For our purposes, a square matrix is basically just a list of items that has to contain a square number of items. We won’t be taking advantage of matrix multiplication or anything like that. This means all the monad operations progress in the same way: wrapping a value creates a singleton, transforming gives you the result of applying a function to each item in the list/matrix, and flattening just inlines the uh… hmm:

The above graphic shows that flattening a square matrix of square matrices can result in a number of items that isn’t a square number. There’s no way to lay them out in a square without creating overlaps or leaving holes.

SquareMatrix would be a monad if only it supported flattening. As things stand, it will have to settle for being an underachieving applicative functor.

Side note for pedants: Technically we could make SquareMatrix into a monad by, say, dropping or duplicating items. I am not going down that road, for it is a really crummy road where every type is a really crummy trivial monad. If you want to get truly technical, then it’s always wrong to say “type X is a monad” because the technical definition of a monad is not a type but involves a type. When I say things like “lists are monads”, what I actually mean is that when making a monad with the list type there are natural, intuitive, and well-behaved operations to pair with it. The same is not true of square matrices: the flatten operation arbitrarily introducing or removing items is neither intuitive nor natural.

It turns out that adding size constraints, and other sorts of constraints, is an easy way to ‘break’ the monad-ness of a type. Other examples of non-monads you can make this way include sets with a minimum number of items, and lists with a maximum number of items (except max 1, which gives you something equivalent to the Maybe monad).

Not a Monad #3: Printers

A printer is roughly the dual of a parser: instead of producing values when given input, it produces output when given values. Parsers are monads, but printers aren’t:

The above graphic shows that, assuming you let me get away with the incredibly unnatural implementation of wrap (after ranting about only counting natural operations..), the only reason printer isn’t a monad is its transformation ends up backwards.

What I mean by backwards is that, when given a function from T1 to T2, you can’t turn a printer of T1s into a printer of T2s but you can turn a printer of T2s into a printer of T1s. The reason this occurs is related to variance.

Printers are contravariant. They vary against changes to their type argument. Suppose a fancy string is a special type of string. A printer for all strings can be used as a printer for fancy strings, but a printer for fancy strings can’t necessarily handle arbitrary strings.

Contrasts that with parsers, which are covariant. Their subtyping relationship matches changes to their type argument. A parser that returns fancy strings can be treated as if it returned arbitrary strings, but a parser that returns arbitrary strings is not guaranteed to always return fancy strings.

Types that are neither contravariant nor covariant are called invariant. Most mutable types fall into this category, with the ability to read items preventing contravariance and the ability to insert items preventing covariance.

Why am I suddenly talking about variance? Because monads are always, in a sense, covariant. You can match subtype relations by using the transform function. So contravariant types like printers, comparers, and actions taking an argument all won’t be monads. This also explains why a Future is a monad, but a FutureSource (a manually controlled future, invariant) is not.

Not a Monad #4: Boolean

Last, and least, is an example so trivial I couldn’t leave it out or bother to make a graphic for it. If you were that student in graph theory who always raised their hand to say “but… what about the empty graph?”, this one’s for you.

Non-generic types, like bools and bytes, can’t be monads because they don’t support wrapping. They can’t store arbitrary values. This is especially clear in the case of a bool: how are you going to distinguish between a wrapped 0, a wrapped 1, and a wrapped 2? There’s not enough states!

(What? The trivial/empty monad? See earlier pedantic note.)

Summary

A monad is a type that supports wrapping, transforming, and flattening.

Quantum superpositions fail to correctly support transforming and flattening, due to interference. Square matrices fail to correctly support flattening, because of their square size constraint. Printers are contravariant so they get transforming backwards. Bools aren’t generic so they can’t even support wrapping.

Discuss on Reddit

Twitter: @CraigGidney

Comments are closed.

Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.

Archive