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:
 Define a data type that encodes various instructions for a given problem space. For example, a
MarsRover a
datatype that canMove a
orFly a
. Thea
represents the final outcome produced by the efforts of ourMarsRover
, which could be a soil sample or a recording of Martian wind.  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
toPickUp
an object, and then we can pattern match on the object, callingLiftRock
if it finds a rock orLiftMartian
if it finds a Martian.  Write an interpreter that interprets our free monad using a second (unfree) 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'sAff
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 monadify 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 monady 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 monadesque. 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 purescripthyrule
. 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 monadocity.
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 purescriptdeku
, 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 monadland, every time we have an Event (Event Nut)
, we'd just call join
to get an Event Nut
. In fact, whenever you leftbind 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 monadland, 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:

createDOMElt
creates a DOM element based on some spec 
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 purescriptfree
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 noop.
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 purescriptdeku
and have it built for you. Either way, free monads for the win!
Top comments (0)