Murat Kasimov

Murat Kasimov

I'm a software engineer who solves real-world problems by using formal methods to build safe and elegant programs as much as possible.

Trying to compose non-composable: monads

9 minute read

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

You May Also Enjoy

A story of an arrow and a comma

9 minute read

Published:

In this article I’m going to show you what are adjoint functors about through real programming examples. We will build a lot of useful stuff just with two simplest constructions: an arrow and a comma.

Cross wolf, goat and cabbage across the river with effects

5 minute read

Published:

Once upon a time a farmer went to a market and purchased a wolf, a goat , and a cabbage. On his way home, the farmer came to the bank of a river and rented a boat. But crossing the river by boat, the farmer could carry only himself and a single one of his purchases: the wolf, the goat, or the cabbage. If left unattended together, the wolf would eat the goat, or the goat would eat the cabbage. The farmer’s challenge was to carry himself and his purchases to the far bank of the river, leaving each purchase intact. How did he do it?