🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Free Monad Interpreters

A free monad interpreter is a function that turns a free program into a real effect. The same program can run under different interpreters with different results.

An IO interpreter performs each step

The IO interpreter prints each line as it meets it. The final result is printed last.

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 LogF next = Say String next
instance Functor LogF where
  fmap f (Say s n) = Say s (f n)
say :: String -> Free LogF ()
say s = Free (Say s (Pure ()))
runLog :: Free LogF a -> IO a
runLog (Pure a) = return a
runLog (Free (Say s next)) = putStrLn s >> runLog next
main :: IO ()
main = runLog (do say "start"; return 5) >>= print

A test interpreter collects steps

The collecting interpreter gathers lines into a list. It never prints while it runs.

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 LogF next = Say String next
instance Functor LogF where
  fmap f (Say s n) = Say s (f n)
say :: String -> Free LogF ()
say s = Free (Say s (Pure ()))
collect :: Free LogF a -> ([String], a)
collect (Pure a) = ([], a)
collect (Free (Say s next)) = let (ss, a) = collect next in (s : ss, a)
main :: IO ()
main = print (collect (do say "a"; say "b"; return 5))

One program, two meanings

The same program can be collected or counted. Both interpreters read the same steps.

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 LogF next = Say String next
instance Functor LogF where
  fmap f (Say s n) = Say s (f n)
say :: String -> Free LogF ()
say s = Free (Say s (Pure ()))
collect :: Free LogF a -> ([String], a)
collect (Pure a) = ([], a)
collect (Free (Say s next)) = let (ss, a) = collect next in (s : ss, a)
countSays :: Free LogF a -> Int
countSays (Pure _) = 0
countSays (Free (Say _ next)) = 1 + countSays next
prog :: Free LogF Int
prog = do say "a"; say "b"; return 5
main :: IO ()
main = do print (collect prog); print (countSays prog)

Example

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 LogF next = Say String next
instance Functor LogF where
  fmap f (Say s n) = Say s (f n)
say :: String -> Free LogF ()
say s = Free (Say s (Pure ()))
collect :: Free LogF a -> ([String], a)
collect (Pure a) = ([], a)
collect (Free (Say s next)) = let (ss, a) = collect next in (s : ss, a)
countSays :: Free LogF a -> Int
countSays (Pure _) = 0
countSays (Free (Say _ next)) = 1 + countSays next
prog :: Free LogF String
prog = do say "red"; say "green"; say "blue"; return "done"
main :: IO ()
main = do print (collect prog); print (countSays prog)

Key points

  • Interpreter: a function that gives meaning to each step of a free program.
  • Fold: the shape of an interpreter, which handles Pure once and each step in turn.
  • IO interpreter: an interpreter that performs each step as a real action.
  • Test interpreter: an interpreter that collects steps instead of performing them.
  • Separation: the program stays the same while the interpreter changes.

In this example, prog joins three say steps with a final result, the collecting interpreter turns the steps into a list beside the result, and the counting interpreter turns the same steps into the number 3.

Note

an interpreter must handle every step type, or the program cannot run.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

Which interpreter is best for testing a free program without side effects?