# Trying to compose non-composable: monads

** Published:**

How many times have you heard “monads do not compose”? I’ve spent a lot of time trying to contradict this statement. But just like in math, if you want to understand something sometimes you have to change your point of view.

It’s recommended to read previous parts of this series: part 1, part 2.

When we want to unite two effects into one (into transformer) we have two options: wrap a left one into a right or wrap a right one into a left. These two options define with `TU`

and `UT`

schemes.

```
newtype TU t u a = TU (t :. u := a)
newtype UT t u a = UT (u :. t := a)
```

As we already know from previous parts for computations with a read-only environment (`Reader`

) it’s enough to have direct composition, but for error handling effects (`Maybe`

and `Either`

) reverse composition `UT`

fits.

```
type instance Schema (Reader e) = TU ((->) e)
type instance Schema (Either e) = UT (Either e)
type instance Schema Maybe = UT Maybe
```

Covariant and Applicative functor instances look pretty obvious because it’s still functor and as we know functors compose.

```
(<$$>) :: (Functor t, Functor u) => (a -> b) -> t :. u := a -> t :. u := b
(<$$>) = (<$>) . (<$>)
(<**>) :: (Applicative t, Applicative u) => t :. u := (a -> b) -> t :. u := a -> t :. u := b
f <**> x = (<*>) <$> f <*> x
instance (Functor t, Functor u) => Functor (TU t u) where
fmap f (TU x) = TU $ f <$$> x
instance (Applicative t, Applicative u) => Applicative (TU t u) where
pure = TU . pure . pure
TU f <*> TU x = TU $ f <**> x
instance (Functor t, Functor u) => Functor (UT t u) where
fmap f (UT x) = UT $ f <$$> x
instance (Applicative t, Applicative u) => Applicative (UT t u) where
pure = UT . pure . pure
UT f <*> UT x = UT $ f <**> x
```

Problem appear when we try to define `Monad`

instances. It’s unclear, how we are going to find generalized method if two effects are unknown.

```
instance (Monad t, Monad u) => Monad (TU t u) where
x >>= f = ???
instance (Monad t, Monad u) => Monad (UT t u) where
x >>= f = ???
```

Perhaps we are not up to it yet. Let’s try instead define instances for one known effects in transformer:

```
instance Monad u => Monad (TU ((->) e) u) where
TU x >>= f = TU $ \e -> x e >>= ($ e) . run . f
instance Monad u => Monad (UT (Either e) u) where
UT x >>= f = UT $ x >>= \case
Left e -> pure $ Left e
Right r -> run $ f r
instance Monad u => Monad (UT Maybe u) where
UT x >>= f = UT $ x >>= \case
Nothing -> pure Nothing
Just r -> run $ f r
```

In case of error handling (`Maybe`

and `Either`

) we can see the same behavior: if invariant contains parameter `a`

then computation goes on. It’s incredibly similar to `Traversable`

! This is how it looks like:

```
class (Functor t, Foldable t) => Traversable t where
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
instance Traversable Maybe where
traverse _ Nothing = pure Nothing
traverse f (Just x) = Just <$> f x
instance Traversable (Either a) where
traverse _ (Left x) = pure (Left x)
traverse f (Right y) = Right <$> f y
```

Let’s try to use it:

```
instance (Traversable t, Monad t, Monad u) => Monad (UT t u) where
UT x >>= f = UT $ x >>= \i -> join <$> traverse (run . f) i
```

It works! It means that we can bind transformers with a known `Traversable`

effect.

But what we should do with `TU`

which used for `Reader`

? I don’t know yet. But we can try something - we take the opposite class for `Traversable`

- `Distributive`

. Such a happy day - there is an instance for `Reader`

(for its inner type `(->) e`

to be precise)!

```
class Functor g => Distributive g where
collect :: Functor f => (a -> g b) -> f a -> g (f b)
instance Distributive ((->) e) where
collect f q e = flip f e <$> q
```

But why exactly these classes and why they’re opposite each other? In order to understand it we can take a closer look at their modified methods where we replace `a -> t b`

functions with `id`

.

```
sequence :: (Traversable t, Applicative u) => t (u a) -> u (t a)
sequence = traverse id
distribute :: (Distributive t, Functor u) => u (t a) -> t (u a)
distribute = collect id
```

That’s it! We can see that these methods let us change the order of effects. If `Traversable`

worked for reverse composition, could `Distributive`

to be fitted for direct one?

```
instance (Monad t, Distributive t, Monad u) => Monad (TU t u) where
TU x >>= f = TU $ x >>= \i -> join <$> collect (run . f) i
```

Yes, it works too! So we have an algorithm to define `Monad`

instances for such transformers:

- Reverse composition
`TU`

- rely on`Traversable`

- DIrect composition
`UT`

- rely on`Distributive`

But we also have a more complicated scheme - `TUT`

which is used for monad `State `

and comonad `Store`

.

```
newtype TUT t t' u a = TUT (t :. u :. t' := a)
newtype State s a = State ((->) s :. (,) s := a)
newtype Store s a = Store ((,) s :. (->) s := a)
type instance Schema (State s) = TUT ((->) s) ((,) s)
type instance Schema (Store s) = TUT ((,) s) ((->) s)
```

Looks pretty complicated, right? The Composition of covariant `Functor`

’s still works, but not for `Applicative`

’s - we can’t just map effectful function to the composition of an arrow and a comma because they’re knitted. In other words, tuple content is dependent of an argument of function and we have to make a function application to get an updated value.

```
instance (Functor t, Functor t', Functor u) => Functor (TUT t t' u) where
fmap f (TUT x) = TUT $ f <$$$> x
```

So, the arrow (`(->) s`

) is `Distributive`

and the comma (`(,) s`

) is `Traversable`

… But there is a more tight connection between these two types called `Adjunction`

(you can read more about it here).

```
class Functor t => Adjunction t u where
leftAdjunct :: (t a -> b) -> a -> u b
rightAdjunct :: (a -> u b) -> t a -> b
unit :: a -> u :. t := a
unit = leftAdjunct id
counit :: t :. u := a -> a
counit = rightAdjunct id
instance Adjunction ((,) s) ((->) s) where
leftAdjunct :: ((s, a) -> b) -> a -> (s -> b)
leftAdjunct f a s = f (s, a)
rightAdjunct :: (a -> s -> b) -> (s, a) -> b
rightAdjunct f (s, a) = f a s
unit :: a -> s -> (s, a)
unit x = \s -> (s, x)
counit :: (s, (s -> a)) -> a
counit (s, f) = f s
```

Let’s try to deal with `State`

effect first. Wrapping into an effect is completely identical to `unit`

method and we use right adjoint to bind two effects in `Monad`

chain.

```
instance Monad (State s) where
State x >>= f = State $ rightAdjunct (run . f) <$> x
/— Or: State x >>= f = State $ counit <$> ((run . f) <$$> x)/
return = State . unit
```

But what about transformers? We have an unknown effect between the two ones. To wrap a value into a transformer we need left adjunction and for binding, we need right adjunction:

```
instance (Adjunction t' t, Monad u) => Monad (TUT t t' u) where
x >>= f = TUT $ (>>= rightAdjunct (run . f)) <$> run x
return = TUT . (leftAdjunct pure)
```

Amazing, to define `Comonad`

instance for the same scheme we need to do everything vice versa:

```
instance (Adjunction t' t, Comonad u) => Comonad (TUT t' t := u) where
extend f x = TUT $ (=>> leftAdjunct (f . TUT)) <$> run x
extract = rightAdjunct extract . run
```

And what we need to do to `lift`

an unknown effect up to the transformer layer? We can use `adjunctions`

here too! Moreover, instances for `Monad`

and `Comonad`

transformers are shocking symmetric…

```
instance (Adjunction t' t, Distributive t) => MonadTrans (TUT t t') where
lift = TUT . collect (leftAdjunct id)
instance (Adjunction t' t, Applicative t, forall u . Traversable u) => ComonadTrans (TUT t' t) where
lower = rightAdjunct (traverse id) . run
```

We can draw some conclusions from what has been said:

- If effect has
`Traversable`

instance - reverse schema`UT`

fits. - If effect has
`Distributive`

instances - direct schema`TU`

fits. - If components of effect form
`Adjunction`

-`TUT`

schema fits.

It turns out that some monads can unite in transformers based on the properties of known effects.

You can find the source of the definitions here. Also, you can take a look at examples of application described effect system here.

## Leave a Comment