Monads are infamous for being badly explained. The category theorist may say “A monad is just a monoid in the category of endofunctors”. The programmer may point to some code as a clear example, but lo, you do not know much of how to read Haskell code.
Fortunately, I don’t like category theory and have little programming experience! So I’m perfectly qualified to explain monads. I will assume some basic mathematical competence, though. I didn’t get monads until I spent a while playing around with concrete examples, so this will be long and concrete-example-heavy.
Basically, what underlying structure do probability distributions, powersets, having a “process failed” error message, and infinite lists have in common? That’s a monad. What they have in common is there’s four basic operations you can do that are analogous in all of the cases. Yes, yes, you can define some of these operations in terms of the others, but going straight for the minimalist foundations doesn’t help with learning something for the first time.
Operation 1: Embedding! Let’s say you’ve got some set X, and a point x that’s in it.You can embed your point as a probability distribution. Just map x to the probability distribution that puts all its mass on x. You can embed your point as a set. Just map x to the set containing only x. You can embed your point into the space X + error (a single extra point representing that something went horribly wrong somewhere). Just map x to… itself. You can embed your point as an infinite list. Just consider the list [x,x,x,x…]
Operation 2: Lifting! Let’s say you’ve got some function f, of type X->Y. You can lift f to a function Delta X -> Delta Y (takes a probability distribution over X, spits out a probability distribution over Y). Just… sample from the distribution on X, apply f to whatever point you drew to get a y, and this random process gives you a probability distribution over Y. You can lift f to a function P(X)->P(Y) (takes a subset of X, spits out a subset of Y). Just… take your subset of X, apply f to all the points in it, bam, you get a subset of Y. You can lift f to a function X+error->Y+error. Just apply f usually, and map the extra error point to the extra error point. You can lift f to a function from lists of stuff in X to lists of stuff in Y. Just apply the function to each entry in the list.
Operation 3: Flattening! There’s a way to go from a probability distribution on probability distributions on X to just a probability distribution on X. Just… randomly draw a probability distribution, randomly draw a point x from whatever distribution you just picked, and… that’s a random process picking points from X. There’s a way to go from a subset of the subsets of X to just a subset of X. Union together the subsets in your family, bam, you’re done. There’s a way to go from (X+error)+error to X+error. Just map the internal and external error points to the same “an error happened” point. For lists… well, if you’ve got a list of lists, you can make a new list by going [entry 1 of list 1, entry 2 of list 2, entry 3 of list 3, entry 4 of list 4…]
Operation 4: Applying! The type signature here is (Delta X) x (X->Delta Y) -> (Delta Y). Ie, if you’ve got a probability distribution on X, and a stochastic function from X to Y, can you get a probability distribution on Y? Yes. Draw a point from x, apply the stochastic function to it to randomly get a y, bam, this is a random process generating points from Y. For powerset, it’d be P(X) x (X->P(Y)) -> P(Y). Ok, we’ve got a subset of X, and a function mapping points in X to subsets of Y. Can we get a subset of Y? Yup, just apply the function to all the x’s in your set, to get a family of subsets of Y, and take the union. For error, it’d be (X+error) x (X -> Y+error) -> Y+error. If you started off with error, the output is error. If you started off with some x, try applying the function-which-might-fail, you’ll either get an error or some point in Y. For lists, it’d be L(X) x (X->L(Y)) -> L(Y). It’s a similar thing as flattening here. Using k for our function from X to lists of stuff from Y, and d for our list of stuff from X, you’d make [entry 1 of k(entry 1 of d), entry 2 of k(entry 2 of d), entry 3 of k(entry 3 of d)…]
It should be kinda weird that all four of these operations, embedding, lifting, flattening, and applying, are analogous between the four cases I brought up. Well, that’s what a monad is. It’s something you can do to types/spaces/sets to make another one. Like going from X to probability distributions over X (probability monad), or subsets of X (powerset monad), or X+error (error monad), or infinite lists of stuff from X (list monad). And it can’t just be any old process, it needs to come equipped with these special functions. There’s gotta be some way to Embed your original space into the monad-y space. There’s gotta be some way to Lift functions between original spaces to be between monad-y spaces. There’s gotta be some way to Flatten two applications of the monad into just one. And there’s gotta be some nice way to Apply monad-y functions (probabilistic functions, set-valued functions, functions that might fail, list-generating functions) to a monad-y input to make a monad-y output.
Now, this is a redundant presentation of the defining functions. You can define some of these functions from some other ones, and there’s also some stuff you’ve gotta check to make sure you got the functions right so they cohere nicely with each other and you didn’t just make up random crap. But the official functions that define a monad are usually pretty obvious. I’m not really sure why they’re so useful in functional programming, but they are.
And that’s a monad! That general sort of pattern.
theartofmadeline
dededos
origamiaround
kaledo-art
pixelskylines
tangentwithtanner
ellievsbear
