Cheatsheet: Free Monad

The free monad allows you to build your own custom monad. This lets you use the do notation for whatever you want.

I find that a lot of the tutorials on the Free monad have too much build-up, and it’s hard to figure out what the code should actually be at the end.

This will start with the example, then move to explaining it.

{-# LANGUAGE DeriveFunctor #-}

import Control.Monad.Free (Free (..))

main :: IO ()
main = runOp exampleProgram

exampleProgram :: Free (IOOp String) ()
exampleProgram = do
  write "enter 'quit' to exit\n"
  inputLoop

inputLoop :: Free (IOOp String) ()
inputLoop = do
  write "enter some words> "
  text <- inputLn
  if text == "quit" then end
    else do
    let nWords = length $ words text
    write $ "you entered: " ++ show nWords ++ "\n"
    inputLoop

write :: a -> Free (IOOp a) ()
write s = Free $ Write s (Pure ())

inputLn :: Free (IOOp a) String
inputLn = Free $ Read Pure

end :: Free (IOOp a) ()
end = Free EndProgram

data IOOp b next
  = EndProgram
  | Read (String -> next)
  | Write b next
  deriving (Functor)

runOp :: Free (IOOp String) () -> IO ()
runOp (Free op) = case op of
  EndProgram -> return ()
  Read f -> do
    line <- getLine
    runOp (f line)
  Write s nextOp -> do
    putStr s
    runOp nextOp
runOp (Pure a) = return a

Import

This imports the Free data type (and all of its constructors) from the module Control.Monad.Free. This package isn’t installed by default. You can get it with cabal install free.

Example program

The main function creates the example program and passes it to the interpreter, runOp.

This program ask you for a line, prints out how many words were in that line, and repeats this until you enter “quit”.

Note that the IO operations write and inputLn are functions we define below. Also note that this doesn’t work with the IO monad. This code is entirely pure, and could be run without ever doing IO for real. This might be useful in a test, for example.

Monad functions

The trio - write, inputLn, and end - are the only functions that the monad provides. Think of them as the “API” of the monad. Note how they just construct instances of Free with instances of our IOOp type.

The Pure () in the Write command means that the write function returns () into the monad.

The Pure in the Read lifts the line read into the Free monad.

In real life, you might create an alias for the Free (IOOp a) b type to clean up the signatures a little bit.

IOOp

The IOOp data type defines the possible operations in the monad. The next field in some of the types refers to the “next” operation that will be run. Its type will end up being (Free IOOp a b).

Note how Read doesn’t hold a next directly, instead it holds a function that takes the input string and returns a next. That function is whatever program logic comes after the read operation.

runOp

runOp “interprets” the language into the IO monad. We could just as easily build an interpreter that gives all fake values for testing.

The (Pure a) branch isn’t used here. Pure is how values are returned from the Free monad.

DeriveFunctor

At the top we have the language flag {-# LANGUAGE DeriveFunctor #-}. This enables writing deriving (Functor) for the IOOp data type. If you don’t want to use language flags, it also works fine to just write the Functor implementation yourself. If you did, it would look like this:

-- what you'd write if you didn't have `deriving (Functor)`:
instance Functor (IOOp b) where
  fmap f EndProgram     = EndProgram
  fmap f (Write b next) = Write b (f next)
  fmap f (Read fnext)   = Read (f . fnext)