🎓 A1Learner
🔍
0 of 47 lessons completed

Haskell Free Monad Patterns

A free monad pattern is a reusable shape for building or running free programs. Smart constructors, small programs, and one fold interpreter are the three shapes used here.

A smart constructor hides the constructors

The say helper builds a Free step without showing it. Program code only calls say.

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 = do runLog (say "hi"); putStrLn "ok"

Small programs join into a larger program

Two one-line programs join with bind. The joined program says both lines in order.

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
hello :: Free LogF ()
hello = say "hi"
bye :: Free LogF ()
bye = say "bye"
main :: IO ()
main = runLog (do hello; bye; return "finished") >>= putStrLn

One fold handles every step

The fold returns at Pure and recurses at each step. Counting shows the fold shape without printing.

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 ()))
countSays :: Free LogF a -> Int
countSays (Pure _) = 0
countSays (Free (Say _ next)) = 1 + countSays next
main :: IO ()
main = print (countSays (do say "a"; say "b"; say "c"; return 0))

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)
welcome :: Free LogF ()
welcome = say "Welcome"
farewell :: Free LogF ()
farewell = say "Goodbye"
main :: IO ()
main = print (collect (do welcome; farewell; return "done"))

Key points

  • Smart constructor: a small helper that hides the Pure and Free constructors.
  • Small program: a short free program that does one job well.
  • Composition: joining small programs with bind into a larger program.
  • Fold interpreter: one recursive function that handles Pure and each step.
  • Reuse: the same small program used in more than one larger program.

In this example, welcome and farewell are small programs built with say, the do block joins them with a final result, and the collecting interpreter turns the joined program into a list beside that result.

Note

a smart constructor keeps the raw constructors out of program code.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Haskell Playground

Exercise

What does a smart constructor do?