Haskell Monad Tutorial № 57005

tl;dr Haskell is weird.

Prologue

Purpose of this tutorial:

After reading this tutorial, the reader should have an intuitive idea of what monads are in Haskell. Said intuitive idea should be enough to fully prepare the reader for other tutorials s/he might want to consult later on.

Constraints:

• The necessary background should merely be “Has created simple programs in Haskell”. Ideally not even that.
• The article should be short and concise enough to be comfortably readable within one sitting.
• Most importantly: A novice should be capable of reading it without his/her eyes glazing over.

Why bother?

Before going on, let us quickly mention a funny yet very pertinent parable. Quoth Wikipedia:

The parable of the blind men and an elephant is a story of a group of blind men who have never come across an elephant before and who learn and imagine what the elephant is like by touching it.

Each blind man feels a different part of the animal's body, but only one part, such as the side or the tusk. They then describe the animal based on their limited experience and their descriptions of the elephant are different from each other.

The moral of the parable is that humans have a tendency to claim absolute truth based on their limited, subjective experience as they ignore other people's limited, subjective experiences which may be equally true.

The reason I mention this is the so-called “Monad Tutorial Conundrum”. Briefly: monads are a very, very abstract thing. In fact, they are the most abstract thing I've had the opportunity to study so far… given as some of my other research interests include fractals and quantum computing, this really says something.

So, to understand monads one must think in a very abstract level, which (at least in my personal experience) takes hideous amounts of mental effort. And because it is so abstract, for each person it “clicks” in a different way… which leads to everyone writing their own tutorial to explaining it –we're already approaching eight bits– each utilising a different crazy and unhelpful simile. The phrase “A Monad is like a burrito” is a running joke for this exact reason.

So… no use wondering if the elephant example above corresponds to reality. We have a real example already, and the elephant is monads.

My aim, then, was to create a tutorial that can explain the details of monads by using concrete examples, in order to spare the reader the ordeal. Thus, first I mention what all monads have in common, then list how it applies in each case. I hope that this can serve as a “stepping stone” for other tutorials, that could explain everything more formally.

Yah, but what are monads useful FOR?

Here's the thing.

Haskell's pure functions necessitate that no side-effects are produced. No state is changed, no I/O is performed, no failure is accepted etc.

C's functions allow any number of side-effects. You could make a function add_ints(int a, int b) that goes on to dump the entire memory on the disk, e-mail it to some alien overlord, invert all the bits in your hard-drive, and fail if exposed to direct sunlight.

Haskell's monads allow that exactly one of those things can happen within a given monad. As soon as you wrap a value in a monad, you allow that side-effect to occur—and only that one. Thus, the kinds of side-effects that can be produced are transparent.

The imperative programmer's obvious retort is that “Well, sanely-written C code does that anyway!” to which the functional programmer's obvious retort is that “Well, Haskell builds the sanity into the language specification!”. And so the language wars continue.

Monads don't have to be siamese twins with function purity by the way, but to an extent they're the tool you use in Haskell when you'd use impurity in other languages; exceptions, sentinel values, out parametres, etc.

Main Body

Introduction

Quick recap: Monads are an abstraction. Here's why they are useful: There are some problems that superficially look really disparate, and monads illustrate how those problems can be solved with very similar methods.

So, what are those problems? Among others…

In Haskell, a function always takes some¹ arguments and returns one result. A function called with the same arguments twice needs to return the exact same thing both times. This can pose problems in dealing with the following situations:

• Input and output, because they depend on a myriad things that change each time
• Functions that might fail because they are not defined over some inputs
• Functions that return a list of possible results, from which one or more must be chosen
• Functions that depend on some state

and so on. Thing is, all of those situations can be solved by “enriching” an ordinary value. The enrichment can come from either adding more information to it, or from necessitating that some action must be taken before the value can be accessed.

Examples:

• Maybe includes a flag that says “Have any computations failed thus far?”
• List includes lots of additional possible values
• Writer includes a log which is changed to illustrate what has happened thus far
• State includes, well, a state value
• I/O includes an I/O action that must happen before we continue
• Company includes a charter that says “The legal interests of all those people here will happen to coïncide”

Now, those things alone don't make a monad. There are 6 things that must be true:

1. You need a way to enrich ordinary values, i.e. to include a “default enrichment function”, that can turn an ordinary value into a Monad. Formally, this function is called return, but we will call it enrich for clarity. So if you have some value x…

   • Maybe.enrich says “This is Just x. No failures yet.”
   • List.enrich says “This is a list that only contains x.”
   • Writer.enrich says “This is x. Nothing has been logged yet.”
   • State.enrich says “This is x, and the state is [default state here]”
   • I/O.enrich says “After you request a value, I shall perform exactly zero I/O actions, then yield x.”
   • Company.enrich says “See this Joe Doe here? Well, that's Joe Doe and Company to you now.”

2. You need to be able to enrich values, in the same way, as many times as you want.

   • A Maybe of a Maybe.
   • A list of lists.
   • A conglomerate of companies.
   • …You get the gist.

3. You need to find some way to combine enrichments of the same type. This is formally called join, but we'll call it combine.

   • Maybe.combine says “If either flag indicates that there's a failure, you get Nothing. Otherwise, you get Just [whatever]”.
   • List.combine says “I have two lists. I shall concatenate them, making a new list where the second list begins where the first ends.”
   • Writer.combine says “Let me add/append this thing to the already-existing log here.”
   • State.combine… does not work as intuitively as we'd hope, so we'll leave it outside for now.
   • I/O.combine says “You need to do both of those actions to get that value.”
   • Company.combine says “Those companies will merge into one. That's why we call this a merger.”

4. You need to define an andThen operator.

   • The andThen operator (formally called bind) is a way to transform functions that take a value and return an enriched one, to functions that take an enriched value and return a combined enrichment. Essentially, you tell the program how it can call first one function andThen one other, and keep both enrichments they'll give you.

   This is easy if you have the combine function above. Intuitively, you store the enrichment somewhere safe, feed the value to the function, take the result and the new enrichment, combine the two enrichments, andThen return the result enriched with the aforementioned combination.

5. The default enrichment must behave as an “identity”.

   • This means that, if you combine the default enrichment with anything at all, it should change nothing.

6. The combine function must be associative.

   • In other words, if you have to combine a bunch of things together, the order in which they were applied should be enough information to derive the result unambiguously, the same way that a jigsaw puzzle yields the same result irrespective of which place you began solving from.

Aaaand… that's about it for a quick-and-dirty introduction.

Further Information

What things are NOT monads?

• Marriage, for instance, is not a monad. A married couple cannot marry another married couple. Furthermore, you cannot take an ordinary citizen and declare him or her married. So most of those points are not fulfilled.
• Also… a burrito is not a fscking monad. You absolutely can get a random food and put it into a tortilla, therefore criterion no. 1 –ie having a “default” enrichment for arbitrary values– is satisfied. However, criterion no. 2 is not satisfied, because (to the best of my knowledge) no-one makes a burrito out of other burritos. So we can't enrich values in multiple levels in this case. ²
• Lastly, “dipping something in paint” is not a monad. You can dip a random thing into paint, so criterion no. 1 is satisfied. Also, if you have something dipped in paint before, you can also dip it again, no problem; criterion no. 2 is satisfied too. But after both layers of paint are dry, you cannot mix them together to create a single combined layer of paint; so this time it's at criterion no. 3 that we stumble.
• I've read that criterion no. 3 is characteristic of monads; if you can achieve it, it said, you certainly have a monad in your hands. I'm inclined to believe it, but I have no concrete proof.

Another monad: Function-that-takes-an-X. Hereafter, for short, Function.

We can tell it has an enrichment because it necessitates that something else is done before we get a concrete value: namely, that we supply an argument first. So the question becomes: Does it satisfy criteria 1-6? The answer to that question is left as an exercise to the reader. (Read: Yes it does, but I'm too lazy to convince you.)

Two hints:

• Enriching a function creates a higher-order function. Or, if you prefer, a function that takes two arguments.
• combine says “Instead of giving this function two separate arguments, take one argument and feed it to the function twice.”
• There is a deep reason for how the bind operator behaves, that involves what happens when you compose a two-argument function with a single-argument function, but this is not the place to explain it.

Finally… continuations.

This is a technique that allows us to make the calculations we want, and then provide a “…and then what?” clause at the end. This is known as Continuation Passing Style, or CPS for short.

Let's imagine that a child asks its mum: “Hey mum! Can I borrow the chainsaw?” and the mum says “Of course! Do whatever you want!”

In this case, the mother acts as a function: Upon an input (“please give me a chainsaw”) it immediately provides an output (the object itself).

Of course, this is a hugely dangerous thing to do. So much so, that her own mother gives her an ultimatum: “Next time you do that, CPS will be involved.”

Now, if the child asks its mum “Hey mum! Can I borrow the chainsaw?” she replies: “…What do you want it for?”

In this occasion, the mother acts as a continuation. That is to say, before outputting a value, she necessitates the provision of another function that will take that value as an input. Of course, getting the actual value is trivial: We just use the identity function (“I just want to see it, please!”) and the value appears just fine.

Let us repeat: Something else must be done before the value is available. That is an enrichment, which ought to make us wonder if a continuation is a monad. As it turns out, it is… but analysing that further is way beyond the scope of this tutorial.

Now, you might ask: What are continuations useful for? Well, let me just tell you this: If you find out, let me know, 'cuz I don't know either.

PS: Many thanks to /u/duplode for clarifications.