monad-embed Tutorial

This tutorial will assume you already know Haskell; it will skip the basics and go straight to the parts of monad-embed that are different from Haskell.

It will also assume you have already read the syntax section, or that you can pick up the syntax as you go along.


Every term in monad-embed has two types associated with it: its type, of kind *, and its flavor, which is a monad of kind * -> *. Type and flavor are often written together using the syntax {flavor} type. The reduction of the term is described in terms of the return and (>>=) operations of its flavor. The details of the reduction process are here.

wrap and unwrap

The built-in wrap and unwrap functions in monad-embed move monad-transformers between an expression's type and its flavor.

wrap takes a value of type and flavor {m} (t m a), where m is a monad and t is a monad transformer. It moves the t transformer from the expression's type to its flavor; the return value of wrap has type and flavor {t / m} a, where / indicates the composition of a monad transformer with a monad.

unwrap does the exact opposite of wrap. It takes a value of type and flavor {t / m} a, and produces a value of type and flavor {m} (t m a).

Using wrap

In general, wrap is used to create side effects. You construct a value of type t m a which describes the side effects, and then you use wrap to convert from a term that explicitly describes the side effects to a term that implicly has the side effects.

For example, suppose that we are using the ZList monad transformer, which is similar to Haskell's ListT. We can use the following code to create a definition that is simultaneously equal to 1 and 2:

oneOrTwo :: (m :: * -> *) => {ZList / m} Number;
oneOrTwo = wrap [ZCons 1 [ZCons 2 [ZNil]]];
oneOrTwo has type Number, but because its flavor is ZList / m, it is internally actually a list of numbers. We use wrap to convert from ZCons 1 [ZCons 2 [ZNil]], which has type and flavor {m} ZList m Number, to oneOrTwo.

We can then use oneOrTwo in other functions in the ZList monad transformer. For example:

pairsOfOneAndTwo :: (m :: * -> *) => {ZList / m} Pair Number Number;
pairsOfOneAndTwo = Pair oneOrTwo oneOrTwo;
Internally, pairsOfOneAndTwo is a list of four values: (Pair 1 1), (Pair 1 2), (Pair 2 1), and (Pair 2 2). If we wanted to just have (Pair 1 1) and (Pair 2 2), we could write this instead:
pairOfOneOrTwo :: (m :: * -> *) => {ZList / m} Pair Number Number;
pairOfOneOrTwo = do { x = oneOrTwo; } then Pair x x;

Using unwrap

Terms that are internally monadic aren't any good if you can't access the internal monad. The unwrap function converts terms of type and flavor {t / m} a into terms of type and flavor {m} (t m a), allowing you to work with the internal monad. For example, suppose that we want to write a program that prints every pair in pairsOfOneAndTwo to the console:

printPairs :: {IO}
              ZList IO (Pair Number Number)
           -> Unit;
printPairs = \ pairs -> case pairs of {
    ZNil -> Unit;
    ZCons (Pair a b) [rest] -> do {
        output (numToStr a `strCat` ", " `strCat` numToStr b);
        } then printPairs rest;

main = printPairs (unwrap [pairsOfOneAndTwo]);
The output from this program is:
Output: 1.0, 1.0
Output: 1.0, 2.0
Output: 2.0, 1.0
Output: 2.0, 2.0

Parameterizing on a monad

oneOrTwo, pairsOfOneAndTwo, and pairOfOneOrTwo are all polymorphic on a monad m. In this example program, m is always instantiated to IO, but this isn't necessary. oneOrTwo and its friends could be used in a function that was itself embedded in another monad on top of IO.

As an example of this, consider a slightly more useful function than oneOrTwo: either. The function either, which is defined in the standard library, takes two arguments of the same type and returns both of them. Of course, this is only possible because it exists in the ZList monad. either is defined as follows:

either :: (f :: * -> *, a :: *) => {ZList / f} [a] -> [a] -> a;
either = \ [x] [y] -> wrap [zcat (unwrap [x]) [unwrap [y]]];
The square brackets [] indicate that the function arguments are passed lazily. (There is no syntactic sugar for lists in monad-embed.) either works by unwrapping both of its arguments into ZLists, concatenating the two lists, and then re-wrapping the concatenated ZLists. We could have defined oneOrTwo as either [1] [2].

either only works in the ZList monad transformer, but it works with any monad under ZList. The following contrived example uses the State monad transformer to sum the alternatives produced by an expression using either:

oneTwoThreeFour :: (f :: * -> *) => {ZList / f} Number;
oneTwoThreeFour = either [1] [either [2] [either [3] [4]]];

sumNumbers :: (g :: * -> *) => {State Number / g} Unit;
sumNumbers = do {
    numbers = lazyToStrictList (unwrap [oneTwoThreeFour]);
    map (num -> setState (getState `plus` num)) numbers;
    } then Unit;

main = do {
    sum = fst (runState 0 (unwrap [sumNumbers]));
    outputNumber sum;
    } then Unit;
In sumNumbers, g is instantiated to IO. In oneTwoThreeFour, f is instantiated to State Number / IO.

Strictness and laziness

In Haskell, side effects are very limited. Besides unsafePerformIO, the side effects of a function are limited to nontermination and raising exceptions via error. In monad-embed, side effects can be anything that can be expressed in the monad that is the flavor of the term. In order to give the programmer more control of exactly when side effects are executed, monad-embed offers strict and lazy variations on functions, do-bindings, and data constructor fields.

A strict function's argument is evaluated exactly once, when the function is called. A lazy function's argument may be evaluated zero or any number of times, depending on how the function uses its argument. Lazy functions obey beta-reduction, but strict functions do not.

fooStrict :: {IO} Unit -> Unit;
fooStrict = \ x -> do { x; x; x; } then Unit;

fooLazy :: {IO} [Unit] -> Unit;
fooLazy = \ [x] -> do { x; x; x; } then Unit;

-- Outputs "hello" once and "goodbye" three times
main = do {
    fooStrict (output "hello");
    fooLazy [output "goodbye"];
    } then Unit;

Strict and lazy data fields are similar. A strict data field is evaluated once, when the constructor is called; in a lazy data field, the side-effects are "preserved" in the data structure and "replayed" wherever it is used. For example:

data Test (f :: * -> *) = {
    Test   -- Constructor with two fields
        [{f} Unit]   -- This one is lazy
        Unit;        -- This one is strict

main = do {
    thing = Test [output "foo"] (output "bar");   -- Outputs "bar"
    output "***";
    case thing of {
        Test [a] b -> do {
            a;   -- Outputs "foo"
            b;   -- Does not output anything
            } then Unit;
    } then Unit;

Strict and lazy do-bindings work similarly.

Note that a variable introduced into scope by a strict function, strict pattern match, or strict do-binding can take on any flavor at the point that it is used, whereas a variable introduced into scope by a lazy function, lazy pattern match, or lazy do-binding has a specific flavor.

Defining monad transformers

monad-embed does not have any user-defined monads. The only monads in monad-embed are the IO monad and monads formed by the / operator from another monad and a monad transformer. Instead of allowing the user to define new monads, monad-embed allows the user to define new monad transformers.

New monad transformers are defined using the transformer keyword:

transformer Constructor (field :: kind) ... where {
    return = ...;
    bind = ...;

The return function should have type

(m :: * -> *, a :: *) => {m} a -> t m a
where t is the transformer. The bind function should have type
(m :: * -> *, a :: *, b :: *) => {m} t m a -> (a -> t m b) -> t m b

For example, the ZList monad transformer, which is equivalent to Haskell's ListT done right, is defined as follows:

data ZList (f :: * -> *) (a :: *) = {
    ZCons a [{f} ZList f a];   -- Tail is lazy; that's why it's called ZList

transformer ZList where {
    return = \ x -> ZCons x [ZNil];
    bind = \ x f -> zconcat (zmap f x);

One interesting thing to notice about this definition is that it looks more like the Haskell List monad than any Haskell monad transformer. The ZList monad transformer never mentions the return or bind operations of the monad that it is parameterized on. Instead, they are used implicitly because return and bind have the flavor of the monad that ZList is parameterized on. (I suspect, but have not proven, that this produces valid monad transformers.)