A fresh take on free monads
Tags: functional
Published: 2023-04-04 08:15:14

---
title: A fresh take on free monads
published: true
description: Yet another free monad tutorial... but with a twist!
tags: functionalprogramming
cover_image: https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wonctj9qcpy5cu6ugdb4.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-01-25 08:29 +0000
---

The internet is awash with [free](https://serokell.io/blog/introduction-to-free-monads) [monad](https://typelevel.org/cats/datatypes/freemonad.html) [tutorials](https://www.tweag.io/blog/2018-02-05-free-monads/), some of which have been written by [yours truly](https://dev.to/mikesol/freeing-free-monads-with-free-adts-5gpi). 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`](https://pursuit.purescript.org/packages/purescript-aff/7.1.0) 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`](https://pursuit.purescript.org/packages/purescript-aff/7.1.0/docs/Effect.Aff#t:Fiber) and [`Event`](https://pursuit.purescript.org/packages/purescript-hyrule/2.3.7/docs/FRP.Event#t: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`](https://pursuit.purescript.org/packages/purescript-hyrule/2.3.7/docs/FRP.Event#t:Event) from [`purescript-hyrule`](https://pursuit.purescript.org/packages/purescript-hyrule). `Event a` represents a stream of `a` that can be subscribed to, very much like an [`Observable`](https://reactivex.io/documentation/observable.html) from [Rx](https://reactivex.io).

`Event` is a [`Functor`](https://pursuit.purescript.org/packages/purescript-prelude/6.0.1/docs/Data.Functor#t:Functor). We can `map` over each `a` emitted by an event, turning it into a `b`.

`Event` is also an [`Applicative Functor`](https://wiki.haskell.org/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`](https://hackage.haskell.org/package/base-4.18.0.0/docs/Control-Applicative.html#v:pure) or [`return`](https://hackage.haskell.org/package/base-4.18.0.0/docs/Control-Monad.html#v: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](https://stackoverflow.com/questions/46913472/how-exactly-does-the-ap-applicative-monad-law-relate-the-two-classes#comment80782167_46913472) that any monad's applicative instance should behave identically to the function `ap`, which is defined as:

```haskell
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`](https://pursuit.purescript.org/packages/purescript-prelude/6.0.1/docs/Control.Apply#v:apply), aka `<*>`, from Applicative functors. You can verify the behavioral equality of `ap` and `apply` in PureScript for all of the common monads.

```haskell
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:

```haskell
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`](https://purescript-deku.netlify.app/), a UI library that has innumerable users in the multiverse and a handful in our corner of it. Deku uses `Event`s 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.

```haskell
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 :microphone:

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`](https://pursuit.purescript.org/packages/purescript-event/1.2.4/docs/FRP.Event#v:keepLatest)). We can do so using `resume` from `purescript-free` like so:

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

The signature of `resume` is:

```haskell
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.

```haskell
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:

```haskell
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:

```haskell
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`](https://purescript-deku.netlify.app/) and have it built for you. Either way, free monads for the win!