[ANN] Monads - the missing monad transformers library

First of all, let me clarify a little bit what a monad transformer is. It looks like, that I didn’t explain thoroughly this concept in the documentation, so I will try to do it here, and then move it to the docs.

A monad transformer of a monad M takes a monad M' as an argument and wraps it into the monad M yielding a new monad that exhibits properties of both M and M'. So transformers are used to create new monads from existing monads. A particular example, that comes to mind is the Couroutine monad, that is usually implemented as a composition of the Continuation monad (that reifies the control flow) with the State monad (that reifies the data flow), giving us a monad that reifies the whole program semantics. I’m not sure whether it is a simple example though, since the Continuation monad is sort of mind-blowing to many people (as well as a concept of the continuation). A real world example, would be BAP’s Primus.Machine monad that is a composition of the Multi State, Result, and Continuation monads, and implements the semantics of the non-deterministic Turing Machine. Moreover, the Primus.Machine monad by itself is also a monad transformer, i.e., it is a functor that takes another monad as an argument and wraps it in the Primus.Machine monad.

In the Monads library, we provide a transformer for each monad, so that you can build your own monads from the twelve base monads that are already in the library. Each monad itself, is actually implemented as an application of its transformer to the Identity monad. This is a common way of building a monad using the transformers - you start with the Identity monad and then wrap it in more and more layers, until you get the satisfactory result.

Given that a transformer is actually a device to create your own monads, and writing a monad is much harder than using a monad, I would suggest to start with implementing a computation (algorithm) that is parametrized by a monad. Then you can start by applying your algorithm to different existing monads, and then to compositions of them. Basically, this is how you should use a monad, you should start with an algorithm, not with a monad.

Also, monads are abstractions, that are so abstract that they can represent several different and orthogonal concepts, i.e.,

  • totality of a computation (whether a computation may diverge)
  • determinism of a computation (whether a computation may yield more or less that one result)
  • data-flow (how a computation handles data effects)
  • control-flow (an order in which computations are evaluated).

So, for a particular generic program it may or may not make sense to parametrize it with one or another concept. The Primus.Machine example is sort of the extreme, as it basically the final object in the caterogy of monads, since it combines all the features of monads: it represents a non-total, non-deterministic computation with reified control and data flow. This is just because the Primus.Machine monad is used to model/study the computations itself, that are the essence of computer science :slight_smile:

In your case, I would start with something more simple. For example, you may try to deal with data structure traversals (i.e., you may find that iter, fold, find and other iterators can be generalized by putting iter into a monad, so that if a user wants to fold over a structure with some state, then the State monad can be used, if it is necessary to short-circuit the traversal, then a totality or a control flow monad can be used. This idea is very essential, when you’re dealing with very complex data structures such as programming languages representations, where instead of using a preprocessor to derive all possible sorts of iterators, we can use one iterator parametrized by a monad).

Later, you may proceed to more complex data structures and implement a computer language interpreter, parametrized by a computation monad. The interpret itself will define the (denotational) semantics of the language. By applying the interpreter to different monads you can build the same language with different flavors, e.g., lazy vs. strict, deterministic vs. non-deterministic, etc. The Bap_primus.Interpreter can be used as a real world example.

7 Likes