Free Monads

Free monads are monads with the bare minimum of properties. They are useful because they can be chained together and interpreted in different ways. The example below shows a program with two interpreters: one that executes the program and one that prints it out.

The best introduction I have found is https://www.haskellforall.com/2012/06/you-could-have-invented-free-monads.html.

Free monads are not installed by default. To install, use stack install free.

This did not work in GHC 9.0.1, even after adding the extra dependencies to stack.yaml – I had to revert to lts-17.02. (April 2021).

If you Google for free monads, you may be led to control-monad-free-0.6.2 on Hackage. This does not work (the symptom is the compilation error “Control.Monad.Free does not export ‘Free'”) and if you have installed it, you will have to unregister it (stack ghc-unregister control-monad-free-0.6.2) and delete it from the snapshot.

The following example is taken from https://www.haskellforall.com/2012/07/purify-code-using-free-monads.html. There is a similar example at https://riptutorial.com/haskell/example/4241/free-monads-split-monadic-computations-into-data-structures-and-interpreters

I have changed the naming conventions: unbound types are ‘a’ and nonspecific variables are ‘x’.

The comments are my first attempt to understand how it works. Corrections are very welcome.

import Control.Monad.Free (Free (..),liftF)
import System.Exit hiding (ExitSuccess)

{-
'a' is the type of the value that will be passed, lifted into the monad type, through the chain of monads.
The function in GetLine must be executed by the interpreter to give a value of the correct type.
-}
data TeletypeF a
  = PutStrLn String a
  | GetLine (String -> a)
  | ExitSuccess

{- 
natural implementation of Functor. 
Note that PutStrLn, GetLine and ExitSuccess are constructors of TeletypeF, not functions from IO and System.Exit.
GetLine uses composition because the parameter is a function rather than a plain value.
-}
instance Functor TeletypeF where
    fmap f (PutStrLn str x) = PutStrLn str (f x)
    fmap f (GetLine      x) = GetLine (f . x)
    fmap f  ExitSuccess     = ExitSuccess

-- only type works here, not data or newtype
type Teletype = Free TeletypeF

{- putStrLn', getLine' and exitSuccess' lift each of the subtypes of TeletypeF into Teletype. They are named with primes to distinguish them from the functions imported from IO and System.Exit. -}
putStrLn' :: String -> Teletype ()
putStrLn' str = liftF $ PutStrLn str ()

getLine' :: Teletype String
getLine' = liftF $ GetLine id

-- Original type was Teletype a. No sensible interpretation would need to pass on a value, so unit is sufficient.
exitSuccess' :: Teletype () 
exitSuccess' = liftF ExitSuccess

{- The interpreter. The case for GetLine passes the result of getLine to the next monad, and uses composition because the parameter is a function.
The expressions around >> and >>= are themselves monads in the context of IO a, and will be lifted to Teletype by the prime functions in echo.-}
run :: Teletype a -> IO a
run (Pure x) = return x
run (Free (PutStrLn str x)) = putStrLn str >>  run x
run (Free (GetLine  x    )) = getLine      >>= run . x
run (Free  ExitSuccess    ) = exitSuccess

{-
alternative interpreter that writes a simplified version of the program to console.
The message "*** Exception: ExitSuccess" is the expected result of the call to exitSuccess..
-}
run' :: Teletype a -> IO a
run' (Pure x) = print "Pure x" >> return x
run' (Free (PutStrLn str x)) = print "putStrLn str" >>  run' x
run' (Free (GetLine  x    )) = print "getLine" >> pure (id "") >>= run' . x
run' (Free  ExitSuccess    ) = print "exitSuccess" >> exitSuccess

{- a program written in the language defined by TeletypeF. Any sequence of commands would work.
-}
echo :: Teletype ()
echo = do str <- getLine'
          putStrLn' str
          exitSuccess'
          putStrLn' "Finished"

main = run' echo

Afterthoughts:

  1. The subtypes of TeletypeF are named after their implementations. In real life, it would be better to name them after their purposes: eg input, output and exit.
  2. In my alternative interpreter, it took a lot of hammering to get the right types. This is something I need to study.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: