## 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

—

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

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst