previous   next   up   top

Free and Freer Monads: Putting Monads Back into Closet

 


 

Introduction

Writing Monad (and now, Applicative and Functor) instances and making sure the monad laws hold are a big part of defining a monad and even a bigger part in exponentially procreating monad tutorials. We argue that all these instances are boilerplate -- avoidable boilerplate. Perhaps because of the Latin-sounding names and the evocation of the highest Math, the petty boilerplate, trivial laws, plain old plumbing have usurped an extraordinary amount of attention. Wouldn't it be refreshing if we could directly think on what an effect does rather than on how the plumbing works.

Free, and now Freer, monads free us from the boilerplate and let us concentrate on the essentials of side-effects. They let us write definitional interpreters for effects, bringing in the tool that worked well in the program language research and practice. There are many excellent explanations of the Free monad, drawing insights from monoids, universal algebra and category theory. The recently popularized Freer monad brought a predicament: Where does it fit in? Does it let us think clearer about effects? Is it also free? If so, how come it has not been anticipated in all those categorical explanations? We tackle these questions below, except for the last one, of which we can only say that none of the several appearances of freer monads came, to my knowledge, via category theory. (Category theory connections did emerge, in hindsight, and did prove insightful.) In contrast to the many free monad explanations, this article takes a lowbrow approach, relying on concrete examples rather than abstract algebra. (Category theory will only be alluded to parenthetically.)

References
FreeState.hs [6K]
The complete code described in the article

Freer Monads and Extensible Effects

 

Classical monads

Our running example is the familiar State monad, representing the effect of accessing and updating one piece of the global mutable state. The common implementation threads the global state throughout the program, letting the two primitives get and put get hold of and replace the state:
     newtype State s a = State{unState :: s -> (a,s)}
     
     get :: State s s
     get = State $ \s -> (s,s)
     
     put :: s -> State s ()
     put s = State $ \_ -> ((),s)
     
     runState :: State s a -> s -> (a,s)
     runState = unState
The operations get and put, with their implied laws, and the interpreter runState are the essential parts; they are what makes State a mutable-state computation. To conveniently use these operations in Haskell programs, however, we need to write the following instances:
     instance Functor (State s) where
         fmap f (State m) = State $ \s -> let (v,s') = m s in (f v,s')
     
     instance Applicative (State s) where
         pure x = State $ \s -> (x,s)
         State f <*> State x = 
             State $ \s -> let (vf,s1) = f s
                               (vx,s2) = x s1
                           in (vf vx, s2)
     
     instance Monad (State s) where
         return x = State $ \s -> (x,s)
         State m >>= k = State $ \s -> let (v,s') = m s in unState (k v) s'

There is a lot of boilerplate: although Applicative and Functor can be expressed in terms of Monad, they still have to be written explicitly. As a matter of fact, all these instances are boilerplate, even the Monad. The most general monad, functor and applicative instances can be defined once and for all and we should never bother with these instances and their laws again.

 

Free Monad

Free monad gets rid of the boilerplate. (The word ``free'' refers to the category theory construction of the left adjoint of a forgetful operation. We show what it means in plain English.) Our State s is a functor, an applicative and a monad. Let us forget the last two: imagine we have deleted the file with the Applicative and Monad instances for State s. As it turns out, nothing is lost: we can still conveniently use State s in our programs, courtesy of the Free monad construction:
     data Free f a where
       Pure   :: a -> Free f a
       Impure :: f (Free f a) -> Free f a
     
     eta :: Functor f => f a -> Free f a
     eta = Impure . fmap Pure
Here the type constructor f has to be a functor: that is, if we have an f a value and we know how to transform any value of type a to a value of type b, we should be able to obtain the f b value. In other words, f should support the map operation. Even shorter: f has to be a member of the type class Functor. As its type says, eta turns any functor f into the monad Free f. Free f is indeed a monad (and a functor and an applicative):
     instance Functor f => Functor (Free f) where
       fmap f (Pure x)   = Pure $ f x
       fmap f (Impure m) = Impure $ fmap (fmap f) m
     
     instance Functor f => Applicative (Free f) where
       pure = Pure
       Pure f <*> m   = fmap f m
       Impure f <*> m = Impure $ fmap (<*> m) f
     
     instance Functor f => Monad (Free f) where
       return = Pure
       Pure a   >>= k = k a
       Impure m >>= k = Impure (fmap (>>= k) m)
Free f has all these properties for any functor f. Once the above instances are introduced, we do not need to write any more monad instances, for state or any other effect. Because the free monad satisfies all -- and only all -- monad, applicative and functor laws, we do not have to bother with proving the monad laws either.

Coming back to our running example: recall that we have forgotten that State s is a monad. We now make it a monad again, this time without writing any monad and applicative instances. We merely have to say:

     type FState s = Free (State s)
and take on the essentials: the primitives getF and putF (for which we can reuse get and put written earlier)
     getF :: FState s s
     getF = eta get
     
     putF :: s -> FState s ()
     putF = eta . put
and the interpreter
     runFState :: FState s a -> s -> (a,s)
     runFState (Pure x) s   = (x,s)
     runFState (Impure m) s = let (m',s') = unState m s in runFState m' s'
We are all set to program stateful computations, for example:
     testState :: FState Int Int
     testState = do 
       putF 10
       x <- getF
       return x
     
     test_run = runFState testState 0
     -- (10,10)

To reiterate, to use the state effect we only had to: define State s and its Functor instance, write get, put, and the interpreter runFState. We tackled the important parts, without getting distracted with the boilerplate instances and boilerplate laws. We later see that even the Functor (State s) instance is unnecessary.

 

Profitable cheating

If we look carefully at runFState we see a lot of similarity with the bind (>>=) operation of the original State s monad. (The reader is encouraged to write join :: State s (State s a) -> State s a and find even more similarity.) We did have to implement and execute something like the monadic bind after all. This sounds like cheating. First of all, this is the right intuition: many formal constructions of category theory indeed look like cheating. Free f does not magically combines one effectful computation f a with another a -> f b: it cannot know how since f is arbitrary. It simply accumulates all these binding points, for us to deal with, en masse, at the end. That is, Free f merely shifts the work from the monad bind (>>=) to runFState.

Still, Free f is not useless: it automatically applies the unit (that is, return-bind) law and associates the bind points in linear order, so runFState has an easier time. In short, Free f does take care of trivialities -- which is what we wanted.

More importantly, Free f helps shift all the work to the interpreter, and hence makes defining effects simpler, and simpler to reason about. Free f allows us to write definitional interpreters for effects. (Definitional interpreters have been unusually productive in programming languages.) We shall see examples soon. Further, the free monad lets us combine monads, solving the problem that besieged monads since their inception.

 

Freer Monad

Recall, we forgot the Monad and Applicative instances of State s, and got them (or, their ersatz copies) back, through the free monad. Free monad gave us the monad and applicative instances for free. As it happens, we may forget even that State s is a functor. With fmap no longer available, the free monad construction does not work. However, there is a way to obtain fmap by formal cheating. If a structure g a does not support the fmap operation, we may still pretend that it does:
     data Lan g a where
       Lan :: g x -> (x -> a) -> Lan g a
     
     instance Functor (Lan g) where
       fmap f (Lan gx h) = Lan gx (f . h)
     
     lan :: g a -> Lan g a
     lan ga = Lan ga id
(Technically, Lan is an instance of the left Kan extension.) Lan g a keeps the arguments of fmap without actually doing any mapping. Still, it has the appearance of a mappable structure, and gives the needed Functor instance and fmap. Therefore, Free (Lan g) is a monad. We have succeeded to turn g a without any special properties into a monad, which we call a freer monad. Haskell Symposium 2015 paper describes an optimal and extensible version. For us here, the following desugared Free (Lan g) will be sufficient:
     data FFree g a where
       FPure   :: a -> FFree g a
       FImpure :: g x -> (x -> FFree g a) -> FFree g a
In contrast to Free f, the type constructor g :: * -> * does not have to be a functor; it can be anything at all. And yet FFree g is surely a functor, an applicative and a monad: FFree g is the monad by its very construction.
     instance Functor (FFree g) where
       fmap f (FPure x)     = FPure (f x)
       fmap f (FImpure u q) = FImpure u (fmap f . q)
     
     instance Applicative (FFree g) where
       pure = FPure
       FPure f     <*> x = fmap f x
       FImpure u q <*> x = FImpure u ((<*> x) . q)
     
     instance Monad (FFree g) where
       return = FPure
       FPure x      >>= k = k x
       FImpure u k' >>= k = FImpure u (k' >>> k)
where
     (>>>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
     f >>> g = (>>= g) . f
is the composition of side-effectful functions (Kleisli composition). (That monads laws hold is best seen categorically, from the fact that FFree g = Free (Lan f). Category theory really shines here: it gives general theorems, which apply in very many specific circumstances.) Any structure g a can be turned into a monad, no matter what it is:
     etaF :: g a -> FFree g a
     etaF fa = FImpure fa FPure
Compared to eta of the free monad, etaF has no Functor constraint and uses no fmap, which is the sign of improved efficiency.

To make our State s a monad, we no longer have to write any instances at all, not even a Functor. We only have to say:

     type FFState s = FFree (State s)
define the primitives
     getFF :: FFState s s
     getFF = etaF get
     
     putFF :: s -> FFState s ()
     putFF = etaF . put
and write the interpreter
     runFFState :: FFState s a -> s -> (a,s)
     runFFState (FPure x) s     = (x,s)
     runFFState (FImpure m q) s = let (x,s') = unState m s in runFFState (q x) s'
That was all we had to do to write programs (e.g., testState) with the state effect.

The ``formal cheating'', the shifting of the work from the monad bind to the interpreter runFFState has become clearer. A typical computation, for example, testState, without syntax sugar looks like

     ((FImpure (put 10) Pure) >>= \_ -> getF) >>= \x -> return x
of the general shape
     (((FImpure eff k1) >>= k2) >>= ...) >>= kn
where eff identifies the effect to perform, and k1,...,kn are the follow-up computations. The bind operation of FFree g turns the above into
     FImpure eff (k1 >>> k2 >>> ... >>> kn)
which is handed over to runFFState to deal with eff and then to follow up. Thus FFree g collects all effect follow-ups k1,...,kn into a sort of a heterogeneous list, with (>>>) playing the role of the list constructor. (One is reminded of the connection between the free monad and the free monoid, which is a sequence.) Thinking of k1 >>> k2 >>> ... >>> kn as a list is not merely amusing. The Haskell 2015 paper has significantly improved the performance of the freer monad by treating k1 >>> k2 >>> ... >>> kn truly as a heterogeneous data structure, an efficient queue.

Looking back to our State s example, we see that we may forget not only return and bind but also the fmap operation, and still recover the state monad as FFree (State s). FFree g is also free (in the category theory/universal algebra sense), and can recover, by formal cheating, the forgotten properties such as fmap or bind. Compared to Free f, the freer monad affords to forget more, and hence has less boilerplate. As a consequence, it is more efficient. Putting it another way, we no longer have to write any basic monad and functor operations and instances in the first place. The freer monad gives them for free.

 

Definitional interpreters for effects

FFree g is a monad for any g whatsoever. This section puts this property of the freer monad to good use. Our implementation of the state effect has been spread around the operations put and get, and the interpreter runFFState. We now pull all the implementation into one place, into the interpreter:
     data StateEff s x where
       Get :: StateEff s s
       Put :: s -> StateEff s ()
     
     type EffState s = FFree (StateEff s)
StateEff s x names the state effect operations and defines their types: one may call it the effect signature. It is not a functor and does not have special properties. Still, FFree (StateEff s) is a monad. The primitives getEff and putEff:
     getEff:: EffState s s
     getEff = etaF Get
     
     putEff:: s -> EffState s ()
     putEff = etaF . Put
no longer access or update the global state; in fact, they do not do anything at all. They merely request what they want to get done: Get the current state, somehow, or update it. The fulfillment of these requests is the job of the interpreter:
     runEffState :: EffState s a -> s -> (a,s)
     runEffState (FPure x) s     = (x,s)
     runEffState (FImpure m q) s =
       let (x,s') = unEffState m s in runEffState (q x) s'
     
     unEffState :: StateEff s a -> (s -> (a,s))
     unEffState Get s     = (s,s)
     unEffState (Put s) _ = ((),s)

Since the entire implementation of the effect is in the interpreter, it becomes the definitional interpreter. It gives the meaning to state and the operations to access and update it. With the implementation in one place, it is easy to see and reason what goes on. It is also easy to change the implementation: to run the same effectful program with a different interpreter -- for example, the one that implements state via a global reference cell or as an exchange of messages with a dedicated process. Not illustrated is the ease to define effect interactions, which is described in the Haskell Symposium 2013 and 2015 papers and the accompanying code.

References
Heinrich Apfelmus: The Operational Monad Tutorial
< http://themonadreader.files.wordpress.com/2010/01/issue15.pdf >
The definitional effect interpreter we have just described is the Operational Monad by Heinrich Apfelmus. Our explanation adds the derivation via the free monad, and hence the easy proof of monad laws. The main difference from Operational is the extensibility and hence the ability to combine monads, which is presented in the Haskell 2015 paper.

 

Performance

Do we have to pay for all the benefits of free and freer monads in performance? With the simplest free and freer monads described so far: yes, the performance suffers.

One should keep in mind that performance does not always matter: a large portion of software we successfully interact with every day is written in Python, Perl or Ruby, and which are not exactly speed kings.

Speeding up the performance of the free monad was the thrust of the Haskell 2015 paper; see also (Jaskelioff&Rivas, ICFP2015) for the closely related but not extensible approach. The optimized freer monad delivers good performance for programs with multiple effects, surpassing monad transformers in speed and memory economy. Even for a single effect, notably State (which GHC optimizes well), the free monad can be on par with the native state monad, see (Wu&Schrijvers, MPC 2015).

 

Conclusions

Free and Freer monads change the way we look at monads. Monad instances and the three laws now appear as boring plumbing, as worthy of a tutorial as a sink. From this angle, the debate of Applicative being a superclass of Monad seems beside the point: we should not be writing any Monad instances at all. Freed from the distraction of monad instances and trivial laws, we can concentrate on effects. Come to think of it, the Freer monad frees us from monads.


Last updated November 6, 2015

This site's top page is http://okmij.org/ftp/

oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!

Converted from HSXML by HSXML->HTML