Sunday, February 19, 2017

In this “monad tutorial” we are not going to learn what monads are, how they are implemented or how they work internally. Instead we are going to look at ten example use cases. We will look at monadic APIs for safe concurrency, build dependencies, stream processing, probabilistic programming, web server programming, mutable references, logic programming, test specification, parsing and HTML5 canvas manipulation.

There is a repository on github with a minimal complete example for each monad discussed. If you want to play with monads you should clone that repository and start from there. Each example in the repository comes with an idea for a small extension. In this post we will only look at a snippet from each example.

The probability monad allows you to describe and compose probability distributions. The following snippet describes the normalized probability of possible outcomes when you roll two twenty-sided dice and take the maximum of the two rolls.

We can execute this transaction atomically. Or we can compose it with other transactions into one big transaction before doing so. In the full example we fork 100001 threads that concurrently try to swap the content of the same two variables.

In software transactional memory we do not block other threads when we want to execute a transaction atomically. We just execute it, watch out for conflicts and roll back if necessary. This rollback is always possible because we know that actions in the STM monad do not have side effects.

Shake is a build system embedded into Haskell. The following snippet describes a build action. It reads a newline-delimited list of file names from the file "shake-data/filenames". It sums the total number of lines in all listed files and writes the result to the file at linecountPath.

Sometimes it is easier or more efficient to express an algorithm imperatively with explicit memory mutation instead of declaratively with immutable data. The histogram function in the following snippet is such an example. In Haskell we use the ST (state thread) monad for this.

The full example exposes a pure histogram function that uses the histogramST function internally and freezes the resulting vector afterwards. This is an example of how monads allow us to keep side-effects local.

A pipe awaits values from upstream and yields values to downstream. The following snippet is a pipe that awaits messages from upstream and only yields them to downstream when the time since the previous message is larger than 3.

The logic monad provides us with a declarative way to to create backtracking search algorithms. In this example we use the expressions function from the following snippet to search for solutions to the four fours puzzle.

The expressions function generates arithmetic expressions that contain exactly the given number of fours. When we have to generate an expression that contains exactly one four we return a constant Four. When we have to generate an expression that contains more than one four we generate a binary operation (Add, Subtract, Mutliply, Divide) between two expressions. We non-deterministically split the number of fours for the left-hand-side and the right-hand-side of the binary operator.

A monadic API is particularly nice for parsing. In this example we parse strings that represent chemical formulas like "H2O" or "NaCl". The following snippet is a part of that parser. It parses a chemical element like "H" or "Na", optionally followed by a decimal number. If there is no number we return a default number of 1.