Monads want to be Free!
(This post is also available as a YouTube video)!
In last week's article I showed how we can use monad classes to allow limited IO effects in our functions. That is, we can get true IO functionality for something small (like printing to the terminal), without allowing a function to run any old IO action (like reading from the file system). In this way monad classes are the building blocks of Haskell's effect structures.
But there's another idea out there called "free monads". Under this paradigm, we can represent our effects with a data type, rather than a typeclass, and this can be a nicer way to conceptualize the problem. In this article I'll show how to use free monads instead of monad classes in the same Nim game example we used last time.
The "starter" code for this article is on the monad-class
branch here.
The "ending" code is on the eff
branch.
And here is a pull request showing all the edits we'll make!
Intro to Free Monads
Free monads are kind of like Haskell Lenses in that there are multiple implementations out there for the same abstract concept. I'm going to use the Freer Effects library. If you use a different implementation, the syntax details might be a bit different, but the core ideas should still be the same.
The first thing to understand about using free monads, at least with this library, is that there's only a single monad, which we call the Eff
monad. And to customize the behavior of this monad, it's parameterized by a type level list containing different effects. Now, we can treat any monad like an effect. So we can construct an instance of this Eff
monad that contains the State monad over our game state, as well as the IO monad.
playGame :: Eff '[State (Player, Int), IO ] Player
Now in order to use monadic functionality within our Eff
monad, we have the use the send
function. So let's write a couple helpers for the state monad to demonstrate this.
getState :: (Member (State (Player, Int)) r) => Eff r (Player, Int)
getState = send (get :: State (Player, Int) (Player, Int))
putState :: (Member (State (Player, Int)) r) => (Player, Int) -> Eff r ()
putState = send . (put :: (Player, Int) -> State (Player, Int) ())
Whereas a typical monad class function won't specify the complete monad m
, in this case, we won't specify the complete effect list. We'll just call it r
. But then we'll place what is called a Member
constraint on this function. We'll say that State (Player, Int)
must be a "member" of the effect list r
. Then we can just use send
in conjunction with the normal monadic functions. We can also add in some type specifiers to make things more clear for the compiler.
Creating an Effect Type
But now let's think about our MonadTerminal
class from last time. This doesn't correspond to a concrete monad, so how would we use it? The answer is that instead of using a typeclass, we're going to make a data type representing this effect, called Terminal
. This will be a generalized algebraic data type, or GADT. So its definition actually kind of does look like a typeclass. Notice this seemingly extra a
parameter as part of the definition.
data Terminal a where
LogMessage :: String -> Terminal ()
GetInputLine :: Terminal String
Now we capitalized our function names to make these data constructors. So let's write functions now under the original lowercase names that will allow us to call these constructors. These functions will look a lot like our state functions. We'll say that Terminal
must be a member of the type list r
. And then we'll just use send
except we'll use it with the appropriate constructor for our effect type.
logMessage :: (Member Terminal r) => String -> Eff r ()
logMessage = send . LogMessage
getInputLine :: (Member Terminal r) => Eff r String
getInputLine = send GetInputLine
Interpretations
At this point, you're probably wondering "hmmmm...when do we make these functions concrete"? After all, we haven't used putStrLn
yet or anything like that. The answer is that we write an interpretation of the effect type, using a particular monad. This function will assume that our Terminal
effect is on top of the effect stack, and it will "peel" that layer off, returning an action that no longer has the effect on the stack.
We call this function runTerminalIO
because for this interpretation, we'll assume we are using the IO
monad. And hence we will add a constraint that the IO monad is on the remaining stack r
.
runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = ...
To fill in this function, we create a natural transformation between a Terminal
action and an IO
action. For the LogMessage
constructor of course we'll use putStrLn
, and for GetInputLine
we'll use getLine
.
runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = ...
where
terminalToIO :: Terminal a -> IO a
terminalToIO (LogMessage msg) = putStrLn msg
terminalToIO GetInputLine = getLine
Then to complete the function, we use runNat
, a library function, together with this transformation.
runTerminalIO :: (Member IO r) => Eff (Terminal ': r) a -> Eff r a
runTerminalIO = runNat terminalToIO
where
terminalToIO :: Terminal a -> IO a
terminalToIO (LogMessage msg) = putStrLn msg
terminalToIO GetInputLine = getLine
Interpreting the Full Stack
Now our complete effect stack will include this Terminal
effect, the State
effect, and the IO
monad. This final stack is like our GameMonad
. We'll need to write a concrete function to turn this in to a normal IO action.
transformGame :: Eff '[ Terminal, State (Player, Int), IO ] a -> IO a
transformGame = runM . (runNatS (Player1, 0) stateToIO) . runTerminalIO
where
stateToIO :: (Player, Int) -> State (Player, Int) a -> IO ((Player, Int), a)
stateToIO prev act = let (a', nextState) = runState act prev in return (nextState, a')
This function is a bit like our other interpretation function in that it includes a transformation of the state layer. We combine this with our existing runTerminalIO
function to get the final interpretation. Instead of runNat
, we use runNatS
to assign an initial state and allow that state to pass through to other calls.
Final Tweaks
And now there are just a few more edits we need to make. Most importantly, we can change the type signatures of our different functions. They should be in the Eff
monad, and for every monad class constraint we used before, we'll now include a Member
constraint.
playGame :: Eff '[ Terminal, State (Player, Int), IO ] Player
validateMove :: (Member Terminal r, Member (State (Player, Int)) r) => String -> Eff r (Maybe Int)
promptPlayer :: (Member Terminal r, Member (State (Player, Int)) r) => Eff r ()
readInput :: (Member Terminal r) => Eff r String
That's most all of what we need to do! We also have to change the direct get
and put
calls to use getState
and putState
, but that's basically it! We can rebuild and play our game again now!
Conclusion: Effectful Haskell!
Now I know this overview was super quick so I could barely scratch the surface of how free monads work and what their benefits are. If you think these sound really cool though, and you want to learn this concept more in depth and get some hands on experience, you should sign up for our Effectful Haskell Course!
This course will teach you all the ins and outs of how Haskell allows you to structure effects, including how to do it with free monads. You'll get to see how these ideas work in the context of a decently-sized project. Even better is that you can get a 20% discount on it by subscribing to Monday Morning Haskell. So don't miss out, follow that link and get learning today!