🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Free Monads Versus MTL

MTL runs a program as it builds it, while a free monad stores the program first and runs it later. That split is the whole difference between the two styles.

MTL runs the reader program at once

The MTL program asks for its value and doubles it. The runner supplies 21.

import Control.Monad.Reader
main :: IO ()
main = print (runReader (do n <- ask; return (n * 2)) 21)

The free version stores the same program

The free program asks and doubles, but stores the steps. Its interpreter supplies 21.

data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Functor (Free f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free x) = Free (fmap (fmap g) x)
instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure g <*> x = fmap g x
  Free g <*> x = Free (fmap (<*> x) g)
instance Functor f => Monad (Free f) where
  Pure a >>= k = k a
  Free x >>= k = Free (fmap (>>= k) x)
data AskF next = Ask (Int -> next)
instance Functor AskF where
  fmap f (Ask k) = Ask (f . k)
askFree :: Free AskF Int
askFree = Free (Ask Pure)
runAsk :: Int -> Free AskF a -> a
runAsk _ (Pure a) = a
runAsk env (Free (Ask k)) = runAsk env (k env)
main :: IO ()
main = print (runAsk 21 (do n <- askFree; return (n * 2)))

One free program, two starting values

The same free program runs under two values. Only the interpreter's starting value changes.

data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Functor (Free f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free x) = Free (fmap (fmap g) x)
instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure g <*> x = fmap g x
  Free g <*> x = Free (fmap (<*> x) g)
instance Functor f => Monad (Free f) where
  Pure a >>= k = k a
  Free x >>= k = Free (fmap (>>= k) x)
data AskF next = Ask (Int -> next)
instance Functor AskF where
  fmap f (Ask k) = Ask (f . k)
askFree :: Free AskF Int
askFree = Free (Ask Pure)
runAsk :: Int -> Free AskF a -> a
runAsk _ (Pure a) = a
runAsk env (Free (Ask k)) = runAsk env (k env)
prog :: Free AskF Int
prog = do n <- askFree; return (n * 2)
main :: IO ()
main = do print (runAsk 21 prog); print (runAsk 10 prog)

Example

import Control.Monad.Reader
data Free f a = Pure a | Free (f (Free f a))
instance Functor f => Functor (Free f) where
  fmap g (Pure a) = Pure (g a)
  fmap g (Free x) = Free (fmap (fmap g) x)
instance Functor f => Applicative (Free f) where
  pure = Pure
  Pure g <*> x = fmap g x
  Free g <*> x = Free (fmap (<*> x) g)
instance Functor f => Monad (Free f) where
  Pure a >>= k = k a
  Free x >>= k = Free (fmap (>>= k) x)
data AskF next = Ask (Int -> next)
instance Functor AskF where
  fmap f (Ask k) = Ask (f . k)
askFree :: Free AskF Int
askFree = Free (Ask Pure)
runAsk :: Int -> Free AskF a -> a
runAsk _ (Pure a) = a
runAsk env (Free (Ask k)) = runAsk env (k env)
prog :: Free AskF Int
prog = do n <- askFree; return (n * 2)
main :: IO ()
main = do print (runReader (do n <- ask; return (n * 2)) 21); print (runAsk 21 prog); print (runAsk 5 prog)

Key points

  • MTL program: a program written against a class like MonadReader that runs at once.
  • Free program: a program stored as data until an interpreter runs it.
  • Ask: the MTL operation that reads a shared value, matched by a free ask step.
  • Interpreter swap: changing a free program's meaning by changing its interpreter.
  • Runner: the function that starts an MTL program with its starting value.

In this example, the MTL program runs at once with 21, the free program runs under the same value for the same answer, and the free program runs again under 5 for a different answer.

Note

MTL is shorter for one fixed meaning, while a free monad is clearer when one program needs several meanings.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

What is the main difference between MTL and a free monad?