A fresh take on free monads

The internet is awash with free monad tutorials, some of which have been written by yours truly. In general, these tutorials follow a similar playbook:

1. Define a data type that encodes various instructions for a given problem space. For example, a MarsRover a datatype that can Move a or Fly a. The a represents the final outcome produced by the efforts of our MarsRover, which could be a soil sample or a recording of Martian wind.
2. Use a free monad to turn this data type into a monad, allowing one to create sequences of instructions and have a logic where future instructions depend on past outcomes. For example, we tell MarsRover a to PickUp an object, and then we can pattern match on the object, calling LiftRock if it finds a rock or LiftMartian if it finds a Martian.
3. Write an interpreter that interprets our free monad using a second (un-free) monad that does something in the real world. For example, with our MarsRover a, we'll likely have asynchronous communication with all sorts of potential error cases, so a monad like PureScript's Aff could be a good fit.

That's all well and good, but there's another use of free monads that doesn't get talked about as much but is just as valuable. Free monads can turn any functor into a monad, which allows you to work with a functor as if it were a monad. So rather than creating a new functor like MarsRover a, we can take an existing functor and use a Free Monad to monad-ify it... at a cost.

Now you may be wondering: "Why can't we just let functors be functors? Why do we have to get all monad-y with them?" In many cases, your favorite functors like Maybe, Identity and Effect are already monads, so there's no need to "free" them. But there are several functors that are not monads, like Fiber and Event, and we may need to work with them in a way that is monad-esque. Enter free monads, the workhorse that allows us to do this.

Event - a functor that's not a monad

As a motivating example, let's consider the type Event a from purescript-hyrule. Event a represents a stream of a that can be subscribed to, very much like an Observable from Rx.

Event is a Functor. We can map over each a emitted by an event, turning it into a b.

Event is also an Applicative Functor. An applicative takes two computational contexts, in this case two event streams, and merges them together in some sensible manner. We can take events A and B of different temporalities and combine them together into a single stream that emits a value every time either A or B emits a value.

Applicatives also allow us to wrap any value in a context, an operation called pure or return. For the case of event, it can turn an arbitrary value a into Event a by guaranteeing that a be present the moment that it is observed.

So why isn't Event a monad? Here it's important to make a distinction between "monad" as a mathematical construct with specific laws and "monad" as a type used in anger for writing code. Many types could theoretically behave in a way that satisfies monadic laws, but that behavior would be confusing and arbitrary in a way that makes writing code with it cumbersome. In these cases, we elect not to write a monad instance for this type.

Event would be both confusing and arbitrary as a monad. It would be confusing because its monadic behavior would not conform to its applicative behavior. Convention dictates that any monad's applicative instance should behave identically to the function ap, which is defined as:

ap :: forall m a b. Monad m => m (a -> b) -> m a -> m b
ap f a = do
  f' <- f
  a' <- a
  pure (f' a')

As you see, the signature of ap is the same as the signature of apply, aka <*>, from Applicative functors. You can verify the behavioral equality of ap and apply in PureScript for all of the common monads.

ap (Just (add 3)) (Just 1) == Just (add 3) <*> Just 1
ap [add 1, add 4] [42] == [add 1, add 4] <*> [42]

When a monad instance of a type is written in a way that violates this rule, it is confusing. In addition to violating the above equalities, it means that the following code blocks would differ in their behavior as well:

ado
  a <- getA
  b <- getB
  in a + b

do
  a <- getA
  b <- getB
  pure (a + b)

No one wants that. So to avoid confusion, we require that applicative and monad instances align in their behavior.

This alignment is impossible to enforce for the Event applicative functor. That's because, if we have an Event (a -> b) and an Event a, we want their temporalities to coexist, with neither temporality taking precedence over the other one. For example, if Event (a -> b) emits 3 times a second and Event a emits 5 times a second, the whole system will emit new values 8 times a second. When Event (a -> b) fires, it does not influence the temporality of Event a, and vice versa. On the other hand, for a monad, the definition of bind as m a -> (a -> m b) -> m b implies that every a can influence the temporality of a new m b. So the behavior of ap, where each a has an effect on m b, would be quite different than that of <*>, where the two streams are independent.

In addition to being confusing, Event's monad instance would also be arbitrary. What would be the "right" way to turn Event (Event a) into Event a, which is what makes a monad a monad (you can join the computational contexts). Every time a new inner event is emitted by the outer event, should the previous inner event be cancelled? That would be reasonable and would avoid emitted values piling up. But it would be equally reasonable to never cancel inner events until the outer event is canceled. While this would be quite noisy, it's also a perfectly valid candidate for a monad instance. Which one do you choose? Tough to say, which is yet another reason that Event can never aspire to the laudable ranks of monad-ocity.

Ok, we get it. Event will never be a monad. We've had our mourning period, but we can't seem to move on because of a pesky problem. What do we do when we encounter an Event (Event a) or, even worse, an Event (Event (Event a))? We have no bind instance to help us out. In the next section, we'll explore how this situation may come about.

Events that emit events that emit...

I'm the lead author and maintainer of purescript-deku, a UI library that has innumerable users in the multiverse and a handful in our corner of it. Deku uses Events for everything. Want to update the text of a button? There's an event for that. Want to change the color of some text? There's an event for that. It's events all the way down, and events are fed by the various clicks, mouse swipes, microphone captures, and other inputs that we use to control a browser.

Where it gets interesting is when an interaction with an element begets entirely new elements. For example, a "more info" button that fetches a detailed biography and presents it to a user. We can think of the button click as one event, and then all of the events within the biography (for example, if it is adorned with its own links and buttons) as events that are engendered by the outer event. So the type is Event (Event Nut), where Nut is a lil' bit of DOM managed by Deku.

You may see where I'm going with this. What if our biography contains another biography, sort of like the talmud is a commentary on commentaries. Well, that's Event (Event (Event Nut)). And pretty soon, we have an indeterminate number of nested events. But at the end of the day, we're not nesting an indeterminate number of web pages. We have one, and ideally we'd like our rendering engine to subscribe to a single event and have it spew all the information needed to fuel a web application. The type of this is Event Nut.

In monad-land, every time we have an Event (Event Nut), we'd just call join to get an Event Nut. In fact, whenever you left-bind in a do context, this is what is going on. There is some m a from which an a is extracted, giving way to an m b, and the monadic interpreter figures out how to combine the m-s from m a and m b in a way that makes sense for that given type. But we are not in monad-land, so we need a way to keep a running stack of Event-s that will, when we hit an interpretation stage, get flattened to a single event to which our engine will subscribe.

Free monad and the deferred join

Simply put, free monads allow you to defer the join operation on a nested functor of arbitrary depth. Then, when you're ready to join stuff during an interpretation stage, you can do whatever you want. Rather than using a join based on a fixed bind instance, you can add whatever sorts of logic you'd like to perform all sorts of nifty optimizations. In the case of Deku, there are all sorts of tricks that keep applications snappy.

But don't take my word for it! Let's see it in action.

myProgram spec = do
  -- liftF lifts our functor into the free monad
  domElt <- liftF (createDOMElt spec)
  if isPicture domElt
      then pure domElt
      else append domElt <$> liftF loremPicsum

Here, we have two functions for working with the DOM that emit events:

1. createDOMElt creates a DOM element based on some spec
2. loremPicsum creates a random image

Because they emit events, neither createDOMElt nor loremPicsum can be used in a do bloc. However, their liftF vicissitudes can. All those problematic aspects of events that prevented Event from being a monad? Poof. Gone. Drops the 🎤

But then what do we do with this do block? Enter resume, the function that allows us to traverse our nested structure and work with it as we please. For example, let's say that we want to flatten our events by only ever keeping the most recent inner event (an operation in PureScript called keepLatest). We can do so using resume from purescript-free like so:

myInterpretedProgram = go $ resume $ myProgram mySpec
  where
  go (Right a) = pure a
  go (Left a) = keepLatest (map go a)

The signature of resume is:

resume :: forall f a. Functor f => Free f a -> Either (f (Free f a)) a

For every nested nested level of the functor Event, we can choose our join operation of choice - in this case, keepLatest for each level. And at the end, we get a simple flattened Event.

If this all seems magical, good. We should never lose a sense of magic and wonderment when looking at code. But unlike Remedios la bella floating into the sky, this code is completely grounded in reality. It's possible because of the recursive definition of the free monad.

data Free f a = Cons (f (Free f a)) | Nil a

If you look back at the definition of resume, the type Either (f (Free f a)) a is isomorphic to Free as defined above, so resume is effectively a no-op.

As we nest our functors to build up a free monad, each layer piles on a new Cons, but we don't ever get a monster type like Event (Event (Event Unit)) because the recursion is handled by the recursive definition of the Free type in the cons branch. A couple more definitions:

liftF :: forall f a. Functor f => f a -> Free f a
liftF fa = Cons (map Nil fa)

bind :: forall f a b. Functor f => Free f a -> (a -> Free f b) -> Free f b
bind (Nil a) fb = fb a
bind (Cons a) fb = Cons (map (flip bind identity) ((map <<< map) fb a))

If this feels a lot like working with a list, it's because that's exactly what's going on. A list is:

data List a = Cons (List a) | Nil

Free uses the exact same recursive definition as List. And just like we can interpret a list my treating it like a monoid (for example, summing up a list of numbers), we interpret a Free monad by treating it like a, well, monad.

Conclusion

So the next time you are working with a functor and think to yourself "Dag nab it, if only this were a monad", you can have your cake and eat it too with the free monad. Of course, no cake is actually free, so you'll have to create a join operation at some point, but this trick will allow you to build monadic systems of unimaginable fantasy from humble functors. Or you could just use purescript-deku and have it built for you. Either way, free monads for the win!