🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Free Monad Idea

A free monad is a program stored as data before it runs. It is built from a Pure value or a Free step that holds one effect and the rest of the program.

Pure holds a finished result

A Pure program has no steps left. Running it returns its result.

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)
runLog :: Free LogF a -> IO a
runLog (Pure a) = return a
runLog (Free (Say s next)) = putStrLn s >> runLog next
main :: IO ()
main = runLog (Pure 42) >>= print

A Free step holds one effect

A Free step says one line, then continues with the rest. The result follows the line.

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)
runLog :: Free LogF a -> IO a
runLog (Pure a) = return a
runLog (Free (Say s next)) = putStrLn s >> runLog next
main :: IO ()
main = runLog (Free (Say "hello" (Pure 3))) >>= print

Bind joins steps into a program

Bind joins small programs in order. Two say steps run before the final result.

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 "one"; say "two"; return 9) >>= print

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 ()))
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 "Welcome"; say "Goodbye"; return "done") >>= putStrLn

Key points

  • Free program: a value that describes steps without running them.
  • Pure: the finished part of a free program that holds a result.
  • Free step: one effect plus the program that follows it.
  • Effect functor: a small type that names one step, like saying a line.
  • Bind: the tool that joins small free programs into one longer program.

In this example, say builds one Free step for each line, the do block joins the two steps with a final result, and runLog prints each line in order before main prints the result.

Note

a free monad here is built by hand, with no extra library.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

What does Pure 7 mean in a free program?