# Composition of side effects

```haskell
{-# LANGUAGE LambdaCase            #-}
{-# LANGUAGE QuantifiedConstraints #-}

import Control.Applicative (liftA2)
import Control.Monad       (ap)
```

On our last lecture, we introduced the Parser monad:

```haskell
type Stream = String

newtype ParseError = ParseError { reason :: String }

newtype Parser a = Parser { runParser :: Stream -> Either ParseError (a, Stream) }
```

In essence, it was a combination of two side-effects: of signaling failure and
of operating a stream state. Remember that we omitted a `Monad` instance for
this type; if you have done it yourself, you should have noticed how tedious it
was to just reiterate the same operations you did while writing instances for
`Either` and `State`.

Lucky for us, we don't have to repeat the same again and again for each monad
you might introduce to your codebase. In this lecture, we'll learn how to
properly compose side effects.

## (Applicative) functors compose; Monads don't

We know that functions can be composed: `\f g x -> f (g x)`. We can try and do
the same with type operators:

```haskell
newtype Compose f g a = Compose { runCompose :: f (g a) }
```

Note that type parameters of `Compose` are different in their meaning: `a` is a
simple type, while `f` and `g` are operators that, given a type, produce another
type. In other words, `f` and `a` have different __kinds__: `a` is simply a
`Type` (also called `*` for brevity) and `f` has kind `* -> *`. Most of the
time, kinds are inferred just like types, but you can always specify the kind
explicitly:

```haskell ignore
newtype Compose (f :: * -> *) (g :: * -> *) (a :: *) = Compose (f (g a))
```

This can be done also to specify more concrete types: for example, the first
definition of `Compose` has slightly more general kinds which can be seen by
typing `:i Compose` in GHCi after loading this `.lhs` file into it.

Now, on to the instances of `Compose`. Every composition of functors is a
functor:

```haskell
instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap h = Compose . fmap (fmap h) . runCompose
```

Moreover, every composition of applicative functors is an applicative functor:

```haskell
instance (Applicative f, Applicative g) => Applicative (Compose f g) where
  pure = Compose . pure . pure
  liftA2 h (Compose x) (Compose y) = Compose $ liftA2 (liftA2 h) x y
```

Things are going great! However, if one tries to write out an instance of a
Monad in the same fashion, he would get stuck:

```haskell ignore
join :: Monad m => m (m a) -> m a
join = (>>= id)

instance (Monad f, Monad g) => Monad (Compose f g) where
  x >>= f = Compose $ _ $ runCompose $ fmap (runCompose . f) x
```

More precisely, he would get stuck because writing out this instance also
requires for `g` to _distribute_ over `f`; in other words, that there exists a
function of a type `forall a. g (f a) -> f (g a)`. Does it exist for any pair of
monads? Sadly, no.

How do we get around this? We could encapsulate it into a typeclass and write
out an instance for each possible pair, but there is a better solution: monad
transformers.

## Monad transformers

The idea is that, instead of providing just a monad of kind `* -> *` which can
be later used as-is, we provide a __monad transformer__ which adds a new
capability to the monad provided by the user (in other words, transforms it).
For example, to provide a capability to short-circuit the computation, we
introduce a __maybe transformer__, in short `MaybeT`:

```haskell
newtype MaybeT m a = MaybeT { runMaybeT :: m (Maybe a) }
```

Notice how monads inside are composed: `Maybe (m a)` would be just "either
`Nothing` or an effectful computation", while `m (Maybe a)` can short-circuit
anywhere inside an effectful computation.

`Functor` and `Applicative` instances can safely replicate instances for
`Compose`:

```haskell
instance Functor f => Functor (MaybeT f) where
  fmap f = MaybeT . fmap (fmap f) . runMaybeT

instance Applicative f => Applicative (MaybeT f) where
  pure = MaybeT . pure . pure
  liftA2 h (MaybeT x) (MaybeT y) = MaybeT $ liftA2 (liftA2 h) x y
```

`Monad` instance replicates instance for `Maybe` except that we need to take `m`
into consideration:

```haskell
instance Monad m => Monad (MaybeT m) where
  MaybeT x >>= f = MaybeT $ x >>= \case
                                    Just y -> runMaybeT (f y)
                                    Nothing -> return Nothing
```

One more important example: to provide a read-only environment of type `e`, a
transformer `ReaderT` is used:

```haskell
newtype ReaderT e m a = ReaderT { runReaderT :: e -> m a } deriving (Functor)

instance Applicative f => Applicative (ReaderT e f) where
  pure = ReaderT . pure . pure
  liftA2 h (ReaderT x) (ReaderT y) = ReaderT $ liftA2 (liftA2 h) x y

instance Monad m => Monad (ReaderT e m) where
  ReaderT x >>= f = ReaderT $ \e -> x e >>= (\a -> runReaderT (f a) e)
```

Notice the common pattern: a transformer `t` is something that takes a base
monad `m` and returns new monad `t m` augmented with new capabilities. This is
encapsulated in a `MonadTrans` class:

```haskell
class (forall m . Monad m => Monad (t m)) => MonadTrans t where
  lift :: Monad m => m a -> t m a
```

Really, this new method `lift` is to be expected: if transformer `t` adds new
capabilities and retains all the old ones, you should be able to embed a
computation of type `m a` into this computation of type `t m a` with added
capabilities. Knowing the `Monad` typeclass, this wordy description can be
expressed in just two laws:

* `lift . return = return`
* `lift (m >>= f) = lift m >>= (lift . f)`

## Base monad

Now, we learned how to add capabilities to the monad using monad transformers;
but what do we take as a base monad? Actually, you can take any monad you like,
for example a `State` monad. But if you look at the definition of `State` monad
in Hoogle, you will see the following:

```haskell ignore
type State s = StateT s Identity
```

So `State` is also defined as a transformer? And with some other monad
`Identity` as a base? Introducing the most basic monad of all, `Identity` monad:

```haskell
newtype Identity a = Identity { runIdentity :: a } deriving (Functor)

instance Applicative Identity where
  pure = Identity
  (<*>) = ap

instance Monad Identity where
  Identity x >>= f = f x
```

Without all the discussion involving transformers, this definition looks useless
the same way 0 looks useless if you've never done addition before. So Identity
monad is like the most basic monad of all, adding no capabilities or
side-effects to the computation whatsoever.