The Free
monad gives you a Monad
for any Functor
. The Free
monad can also be used to construct extensible effect systems. I never understood why Free
why this was the case. It turns out it is deeply connected to their ability to yield monads for functors.
For a warmup, lets review Free
1:
data Free f a where
Pure :: a -> Free f a
Free :: f (Free f a) -> Free f a
Free
allows you to build up an AST which describes monadic actions for any given Functor
and defers the interpretation of that AST to a later date. In other words, Free
breaks apart the syntax and semantics of your monadic effects and lets you describe effects syntacally without assigning them any sort of semantics.
How does that work?
Looking at Free
's constructors they bear a striking resemblence to pure
and join
:
pure :: Applicative f => a -> f a
Pure :: a -> Free f a
join :: Monad m => m ( m a) -> m a
Free :: f (Free f a) -> Free f a
Squint your eyes and ignore the Free
type constructors and you can see the symmetry here. The chief difference is that Free
's data constructors lack Applicative
and Monad
constraints. This is because it doesn't actually perform any effects, it is merely a syntax tree describing effects yet to be interpreted.
Now lets take a closer look Free
's Typeclass instances.
instance Functor f => Functor (Free f) where
fmap :: (a -> b) -> Free f a -> Free f b
fmap f (Pure a) = Pure (f a)
fmap f (Free m) = Free $ fmap (fmap f) m
instance Functor f => Applicative (Free f) where
pure :: a -> Free f a
pure = Pure
liftA2 :: (a -> b -> c) -> Free f a -> Free f b -> Free f c
Pure a) m = fmap (f a) m
liftA2 f (Free a) m = Free $ fmap (flip (liftA2 f) m) a
liftA2 f (
instance Functor f => Monad (Free f) where
return :: a -> Free f a
return = Pure
(>>=) :: Free f a -> (a -> Free f b) -> Free f b
>>=) (Pure a) f = f a
(>>=) (Free a) f = Free $ fmap (>>= f) a (
There are two things to notice here:
For all instances f
need only be a Functor
.
These instances are utterly boring and essentially just serve to thread f
's fmap
throughout the syntactic structure of the Free
data constructors.
Both of these points bring home the fact that Free
really only deals with syntax. If we want a semantics for our monadic structure then we must create one via an interpreter.
For example, in Oleg's Paper2 he gives an example of modeling the State
monad in Free
:
eta :: Functor f => f a -> Free f a
= Free . fmap Pure
eta
type FState s = Free (State s)
getF :: FState s s
= eta get
getF
putF :: s -> FState s ()
= eta . put
putF
runStateF :: FState s a -> s -> (a, s)
Pure x) s = (x, s)
runStateF (Free m) s =
runStateF (let (m', s') = runState m s in runStateF m' s'
Here we have chosen State
as our functor and we use eta
to lift state operations into Free
. We use those lifted operations to create a syntax tree describing our stateful program.
We then implement the semantics of our State
effect via the interpreter runStateF
. The intepreter recurses through our Free
AST and interprets the Free
data constructors as the operations of our State
effect. Thus we have recreated the monadic operations of the State
monad via the State
Functor
and Free
's data constructors.
Armed with a reasonable understanding of Free
we can approach the main topic of this blog post. How does seperating the syntax and semantics of monadic effects help us with composing our effects?
Well, it is actually quite simple! Monads do not compose, but functors do compose. Free
allows us to construct a Monad
for any Functor
. Therefore, if we can somehow compose our functors then we can use Free
to produce a Monad
with the composed effects of the two functors.
The Compose
newtype gives us a Functor
made up of right-to-left composition of our functors, but this won't do what we want. We don't want to combine our effects functorily, rather we want access to both f a
and g a
within a single monadic context.
In other words, we want the Sum
of two functors:
data Sum f g a = InL (f a) | InR (g a)
deriving Functor
We need Sum
rather then Either
so that both nested functors use the same a
parameter. With Either
we would only have a Functor
over the Right
term.
With Sum
we can create the world's simplest effects system. In this system we will be able to pick two Functors
patch them into Free
and then write an interpreter to compose their effects.
Our Effect Monad
will look like:
type SimplestFX f g = Free (Sum f g)
For a first attempt we will hardcode our interpreter for State
and Either
:
runFX :: s -> SimplestFX (State s) (Either e) a -> Either e (a, s)
Pure a) = Right (a, s)
runFX s (Free (InL m)) = let (m', s') = runState m s in runFX s' m'
runFX s (Free (InR (Left e))) = throwError e
runFX s (Free (InR (Right m))) = runFX s m runFX s (
All State
operations are in left branch of our Sum
and all Either
operations are in the right branch. This allows our interpreter to know exactly what effect to perform as we traverse the AST.
We lift our effects using eta . InL
and eta . InR
to lift into the left and right branches of the Sum
respectively.
Now we can rewrite the Tree Traversal example from my prevous post on Monad Transformers:
type VariableName = String
type Variables = S.HashSet VariableName
data AST a = Leaf a | Node (AST a) (AST a)
deriving (Show, Functor, Foldable, Traversable)
assignIndexToVariables :: AST VariableName -> Variables -> SimplestFX (State (M.Map VariableName Int)) (Either String) (AST Int)
= forM ast $ \var -> do
assignIndexToVariables ast variables `S.member` variables) $
unless (var $ InR $ throwError $ "Unknown Variable " <> var
eta <- eta $ InL get
cache case M.lookup var cache of
Just index -> pure index
Nothing -> do
let index = M.size cache
$ InL $ put $ M.insert var index cache
eta pure index
main :: IO ()
=
main let vars = S.fromList ["a", "b", "c"]
= Node (Leaf "a") (Node (Leaf "b") (Node (Leaf "a") (Leaf "c")))
ast in print $ runFX mempty $ assignIndexToVariables ast vars
In our last example, the interpreter consists of structural recursion on Free
along with explicit interpretations of our effects into some hard coded result type Either e (a, s)
. We can break up the recursion and interpretation to give us a more general API:
runFX' :: Monad m => (forall x. f x -> m x) -> (forall x. g x -> m x) -> SimplestFX f g a -> m a
Pure a) = pure a
runFX' _ _ (Free (InL f)) = let m = interF f in m >>= runFX' interF interG
runFX' interF interG (Free (InR g)) = let m = interG g in m >>= runFX' interF interG runFX' interF interG (
Now we write an interpreter into some concrete Monad
with the semantics we desire:
runApp :: Monoid s => SimplestFX (State s) (Either e) a -> ExceptT e (State s) a
= runFX' lift (ExceptT . pure) runApp
And finally we run our effects using the transformer stack we interpreted our program into:
main :: IO ()
=
main let vars = S.fromList ["a", "b", "c"]
= Node (Leaf "a") (Node (Leaf "b") (Node (Leaf "a") (Leaf "c")))
ast in print $ flip evalState mempty $ runExceptT $ runApp $ assignIndexToVariables ast vars
In this case we are using ExceptT e (State s) a
but we can choose any semantic context we desire. This reveals another super power of Extensible Effects.
We can use the exact same syntactic construction, eg. code, and have multiple semantic interpretations. For example, we could have a program that performs some calculation and then dispatches the calculation result to some store. We would be able to swap out store interpretations between writing to a file on disk, writing to a database, and sending out an HTTP request, etc.
At this point our effect system can only handle two effects and they must have Functor
instances.
We can replace Sum
with an open union to be able to include an arbitrary number of effects in our program. Haskell does not support open unions natively but we can use some type level tricks to support them.
We can also use Coyoneda
to construct the Freer Monad
which removes the requirement of having a Functor
instance for our types! I'll cover all of this in a later blog post.