Monad Composition Example

This repo is a training project for playing with monads and composition of monads.
For this purpose I wrote a simple module called Pascal for solving really simple math expression. An example is the following:

Pascal.solve "40+2" @?= Right 42

Using git tag and branch you are able to switch to the particular implementation of the algorithm.
The journey starts with a "pure" implementation and ends with a "three level monad composition" implementation (ExceptT StateT WriterT).
Please refer to the test folder to understand how to use the module Pascal.

I hope this example project could help people to understand monad, monad transformers and composition. Writing this code I understood monad better and I learned a lot of new stuff.

How to run the code

There are two way to run the code.

Cabal

cabal test

Docker

./build.sh
docker run --rm cescobaz/monad-composition-example

Dependencies

The only dependencies needed to build a monad composition is transformers. But have a look at mtl (that depends itself from transformers) if transformers is not enough.

Pure computation using Either monad

First of all I want to write a "pure" computation that can fails. So I use Either becuase I like to know whats wrong in case of error.

git checkout pure-computation-using-either-monad

I want to hide the real type so I define a new type as an alias of Either.

type PascalM a = Either String a

Now I can implement the core code.

solve :: String -> PascalM Int

I prefer to use Either as a monad like this:

parseNumber s (x : xs)
    | isDigit x = parseNumber (s ++ [ x ]) xs
    | x == '+' && not (null s) = (+) l <$> parseNumber "" xs
    | otherwise = Left ("unexpected " ++ [ x ])
  where
    l = read s

I don't like to use pattern matching

git checkout pure-computation-using-either-monad-pattern-matching

parseNumber s (x : xs)
    | isDigit x = parseNumber (s ++ [ x ]) xs
    | x == '+' && not (null s) = case (parseNumber "" xs) of
        Right r -> Right (r + l)
        Left err -> Left err
    | otherwise = Left ("unexpected " ++ [ x ])
  where
    l = read s

One level of monad composition: ExceptT

To start monad composition I need a transformer. Beacuse I use Either, ExceptT is the natural monad transformer.

git checkout one-level-monad-composition

Monads are like a computation, a computation where only some behavior are allowed.

To create you own monad (ready to be composed):

define your monad transformer type based on a transformer;

type PascalT m a = ExceptT String m a

define your transformer runner;

runPascalT :: (Monad m) => PascalT m a -> m (Either String a)
runPascalT = runExceptT

Transformer runner will execute the monad (ExceptT in this case) and pop out the inner monad m, ready to be runned by another runner.

define your monad type;

-- before
type PascalM a = Either String a
-- after
type PascalM a = PascalT Identity a

Because of run*T will pop out the inner monad m, at some poit we need stop the composition and we can do it by using an Identity monad that does nothing than give as the value a.
If you need to use IO in your monad you can use IO insted of Identity.

define your monad runner.

runPascal :: PascalM a -> Either String a
runPascal = runIdentity . runPascalT

Done, now I need just a little adjustments on the original code:

-- how to create error / Left ...
-- before
parseNumber "" "" = Left "unexpected end of input"
-- after
parseNumber "" "" = throwE "unexpected end of input"

-- how to call my solver ...
-- before
Pascal.solve "40+2" @?= Right 42
-- after
Pascal.runPascal (Pascal.solve "40+2") @?= Right 42

Two level of monad composition: ExceptT StateT

Ok, I would like to remember all the expression the users ask me so I can avoid repeating the computation.
Lets add a state to my monad by adding StateT.

git checkout two-level-monad-composition

The type of app monad is the same, but the generic m is now wrapped by an other monad: the StateT monad transformer.

-- before
type PascalT m a = ExceptT String m a
-- after
type PascalT m a = ExceptT String (StateT Memory m) a

Transformer runner needs to run also the StateT transformer. Just add it (with the initial state).

-- before
runPascalT :: (Monad m) => PascalT m a -> m (Either String a)
runPascalT m = runExceptT m
-- after
runPascalT :: (Monad m) => PascalT m a -> Memory -> m (Either String a)
runPascalT m = evalStateT (runExceptT m)

Then change the monad runner adding the initial state.

-- before
runPascal :: PascalM a -> Either String a
runPascal m = runIdentity (runPascalT m)
-- after
runPascal :: PascalM a -> Either String a
runPascal m = runIdentity (runPascalT m (Memory [] 0))

Now it is possible to use State monad functions like get, put or modify inside your app monad using lift as prefix.
If you are using transformer lib you need to use lift operator to add monad.

Note that your app monad interface doesn't changed, so you don't need to change tests.

Three level of monad composition: ExceptT StateT WriterT

For the last layer I would like something that could tell me the steps that my algorithm is going through, so I opted for WriterT.

git checkout main

Start from the type of the app monad: just replace m with the new transformer:

-- before
type PascalT m a = ExceptT String (StateT Memory m) a
-- after
type PascalT m a = ExceptT String (StateT Memory (WriterT String m)) a

Then call the relative runner in our app runner:

-- before
runPascalT :: (Monad m) => PascalT m a -> Memory -> m (Either String a)
runPascalT m = evalStateT (runExceptT m)
-- after
runPascalT :: (Monad m) => PascalT m a -> Memory -> m (Either String a, String)
runPascalT m memory = runWriterT (evalStateT (runExceptT m) memory)

I changed the output type to a tuple with the "old" result plus the output of WriterT, a String in this case.

Accordingly I correct the main runner.

-- before
runPascal :: PascalM a -> Either String a
runPascal m = runIdentity (runPascalT m (Memory [] 0))
-- after
runPascal :: PascalM a -> (Either String a, String)
runPascal m = runIdentity (runPascalT m (Memory [] 0))

Ok, now is time to use the new WriterT layer, but at this time it is necessary to call lift two times, e.g.:

tell :: Monad m => String -> PascalT m ()
tell = lift . lift . Control.Monad.Trans.Writer.tell . (:) ':'

Conclusions

It takes me a lot of time to understand monads and monad composition. But now I think I could start to use it in my application understanding what I'm writing.
For sure I understand one thing: read carefully the types of everything and search for a function that match it and you are (more or less) done.

cescobaz/haskell-monad-composition