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.)
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.
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.
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.
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 xof the general shape
(((FImpure eff k1) >>= k2) >>= ...) >>= knwhere
eff identifies the effect to perform, and k1,...,kn are
the follow-up computations. The bind operation of FFree g turns the
above intoFImpure 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.
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.
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).
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.oleg-at-okmij.org
Your comments, problem reports, questions are very welcome!
Converted from HSXML by HSXML->HTML