Combining monads with natural transformations

One of the aspects which sets Haskell apart from other programming languages is that we tend to handle our effects with care. We are used to using monads to encode side effects; for example we use Either e to encode failures, Reader r to describe configuration and State s for stateful operations.

This introduces the issue of combining multiple effects needed in the same computation. Many solutions to this problem were proposed through the years, from monad transformers, to mtl, to more advanced effect systems.

In this blog post I’d like to present an alternative approach which appears quite natural to me, but I was not able to find already implemented and used in the wild. As far as I can see, it hits a nice spot in the scale between simplicity and complexity and deserves to be explored further.

I’m very interested to receive feedback on these ideas and see what other people think of them.

Natural transformations

Let’s start from the main ingredient of our recipe and briefly introduce natural transformations.

If we want to execute two operations f :: m1 a and g :: m2 b together in the same context, we first need to find a monad m where both f and g could live and have a meaning.

To do this, we want a mechanism to interpret operations defined in a context m into another context n. A natural transformation is nothing else but a way to do that in a uniform (i.e. natural) way.

Let’s define a natural transformation with a typeclass¹

class Embeds m n where
    embed :: forall (a :: Type) . m a -> n a

This means that for every type a, we have a function from m a to n a. In other terms, we have a way to transform every operation in the m context into an operation in the n context.

Now, if we come back to our f :: m1 a and g :: m2 b operations, we see that we can interpret both f and g in any context m which admits a natural transformation from m1 and a natural transformation from m2.

f&g :: (Monad m, Embeds m1 m, Embeds m2 m) => m b
f&g = do
  embed f
  embed g

This way, we can execute f and g together in the same operation f&g.

Natural natural transformations

Being able to write f&g to combine two operations from different contexts is nice, but we’re still missing a key ingredient: writing the instances for the Embeds class.

How hard is it? Do we really need to write an instance by hand every time we want to interpret an operation in a more general context?

Luckily the answer to the second question is often no, and writing just very few instances could take us a very long way².

Let’s start to think about what some obvious instances could be.

The most obvious one is probably

-- | (1)
instance Embeds m m where
  embed :: m a -> m a
  embed = id

stating that you can embed any m into itself.

Another easy one is

-- | (2)
instance (Applicative m) => Embeds Identity m where
  embed :: Identity a -> m a
  embed = pure . runIdentity

which states that, for any applicative functor m, it’s possible to embed Identity into m.

The next two instances are a bit more complex.

-- | (3)
instance (Monad m, MonadTrans t, Embeds n m) => Embeds n (t m) where
  embed :: n a -> (t m) a
  embed = lift . embed

This says that whenever we already have that Embeds n m, it is also true that Embeds n (t m), if m is a monad and t is a monad transformer.

-- | (4)
instance {-# OVERLAPPING #-} (Monad n, MFunctor t, Embeds n m) => Embeds (t n) (t m) where
  embed :: t n a -> t m a
  embed = hoist embed

The last one³ says that, whenever Embeds n m, we can deduce that Embeds (t n) (t m), provided that n is a monad and t is an MFunctor.

An explanatory example

To better understand why the above instances make sense, let’s have a look at a concrete example.

Let’s say we have a monad transformer stack type Foo r s = ReaderT r (StateT s IO).

With the above instances, we can deduce Embeds (Reader r) (Foo r s), Embeds (State s) (Foo r s) and Embeds IO (Foo r s).

To jump to the motivation, this allows you to write code like

foo :: Foo r s c
foo = do
  a <- embed (ioOperation :: IO a)
  b <- embed (readerOperation a :: Reader r b)
  embed (statefulOperation a b :: State s c)

and combine operations from different contexts in the same operation.

We can deduce Embeds (Reader r) (Foo r s) in two steps:

• both Reader r = ReaderT r Identity and Foo r s = ReaderT r (StateT s IO) are of the shape t m, hence we can use our last instance (4) and be left to deduce Embeds Identity (StateT s IO);
• the second instance (2) we introduced in the previous paragraph is exactly what we need to conclude.

To deduce Embeds (State s) (Foo r s), we can proceed as follows:

• the only instance that applies is (3). To satisfy it we are left with Embeds (State s) (StateT s IO);
• since both State s = StateT s Identity and StateT s IO are of the shape t m, we can use (4) and be left with Embeds Identity IO;
• now (2) allows us to conclude.

Lastly, we can deduce Embeds IO (Foo r s) as follows:

• the only instance that applies is (3). Applying it, we are left with Embeds IO (StateT s IO);
• again, the only instance that applies is (3). To use it, we need an instance of Embeds IO IO;
• that is granted by our first instance (1).

Relation with mtl

A natural question which might arise, looking at such an approach, is how it compares with mtl.

For example, how does Embeds (Either e) m relate to MonadError e m? Or Embeds (Reader r) m with MonadReader r m?

It’s easy to show that one implication holds: for example, we could have

instance (MonadError e m) => Embeds (Either e) m where
  embed :: Either e a -> m a
  embed (Left e) = throwError e
  embed (Right a) = pure a

and

instance (MonadReader r m) => Embeds (Reader r) m where
  embed :: Reader r a -> m a
  embed (ReaderT f) = reader (runIdentity . f)

At the moment of writing, I have no clear idea whether the other implication (i.e. whether, for example, Embeds (Either e) m implies MonadError e m) should hold, making the two approaches equivalent.

Possibly, an equivalence might hold, if we restrict the type of natural transformations allowed in the Embeds typeclass. One possibility is to consider only monomorphic natural transformations.

In any case, the Embeds approach does not suffer from the n^2 issue, which affects mtl.

If you need to introduce a new effect, you need to define a monad m and a monad transformer t such that m is isomorphic to t Identity and implement the MonadTrans t and Mfunctor t instances.

At that point, the above-defined instances (1) to (4) will do all the hard work.

Hiding natural transformations

Being able to combine functions living in different contexts using Embeds could already be a nice cake, but, if we like it, we can add a cherry on top.

First thing, using Embeds we can define a more general version of >>=

(>>=) :: (Monad m, Embeds n1 m, Embeds n2 m) => n1 a -> (a -> n2 b) -> m b
(>>=) n1a an2b = embed n1a Prelude.>>= (embed . an2b)

This custom (>>=) allows us to sequence computations which live in different monads, using the Embeds machinery.

At this point, we can add just a tiny bit of black magic, in the form of the RebindableSyntax GHC extension. It allows us, among other things, to interpret do notation with the >>= operation which is in scope and not the one from Prelude.

This allows the following code to compile correctly, if our custom >>=⁴ is in scope:

{-# LANGUAGE RebindableSyntax #-}

ioOperation :: IO ()

statefulOperation :: State Int ()

combineTheTwo :: StateT Int IO ()
combineTheTwo = do
  ioOperation
  statefulOperation

This is probably going a bit too far from usual Haskell, since it hides many things under a lot of magic. But if you like it, feel free to use it!

Conclusion

In Italy, we have a saying that goes like “Not everything that shines is gold”. Even if, from the short presentation given in this post, this approach might seem nice, there could be some dark corners. One aspect is that using an approach like this where the types are less strict, you lose type inference, and hence you need to provide more type annotations to help the compiler. Then, there’s probably other subtle issues I didn’t encounter yet. If you notice them, please let me know.

This is not to say that this approach is flawed, but just that it comes with its pros and cons, and it needs to be evaluated carefully.

The last thing I need to say trying to wrap this up is that all of this is really in alpha state, and more work needs to be done to prove it’s actually something useful to have.

If you want to discuss further or contribute, I’m using https://github.com/marcosh/embeds as a repository for all the code related to these ideas. Feel free to open issues there or to contact me directly.