Haskell Language Free Monads How do foldFree and iterM work?
Example
There are some functions to help tear down Free computations by interpreting them into another monad m: iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> (Free f a -> m a) and foldFree :: Monad m => (forall x. f x -> m x) -> (Free f a -> m a). What are they doing?
First let's see what it would take to tear down an interpret a Teletype a function into IO manually. We can see Free f a as being defined
data Free f a
= Pure a
| Free (f (Free f a))
The Pure case is easy:
interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = _
Now, how to interpret a Teletype computation that was built with the Free constructor? We'd like to arrive at a value of type IO a by examining teletypeF :: TeletypeF (Teletype a). To start with, we'll write a function runIO :: TeletypeF a -> IO a which maps a single layer of the free monad to an IO action:
runIO :: TeletypeF a -> IO a
runIO (PrintLine msg x) = putStrLn msg *> return x
runIO (ReadLine k) = fmap k getLine
Now we can use runIO to fill in the rest of interpretTeletype. Recall that teletypeF :: TeletypeF (Teletype a) is a layer of the TeletypeF functor which contains the rest of the Free computation. We'll use runIO to interpret the outermost layer (so we have runIO teletypeF :: IO (Teletype a)) and then use the IO monad's >>= combinator to interpret the returned Teletype a.
interpretTeletype :: Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = runIO teletypeF >>= interpretTeletype
The definition of foldFree is just that of interpretTeletype, except that the runIO function has been factored out. As a result, foldFree works independently of any particular base functor and of any target monad.
foldFree :: Monad m => (forall x. f x -> m x) -> Free f a -> m a
foldFree eta (Pure x) = return x
foldFree eta (Free fa) = eta fa >>= foldFree eta
foldFree has a rank-2 type: eta is a natural transformation. We could have given foldFree a type of Monad m => (f (Free f a) -> m (Free f a)) -> Free f a -> m a, but that gives eta the liberty of inspecting the Free computation inside the f layer. Giving foldFree this more restrictive type ensures that eta can only process a single layer at a time.
iterM does give the folding function the ability to examine the subcomputation. The (monadic) result of the previous iteration is available to the next, inside f's parameter. iterM is analogous to a paramorphism whereas foldFree is like a catamorphism.
iterM :: (Monad m, Functor f) => (f (m a) -> m a) -> Free f a -> m a
iterM phi (Pure x) = return x
iterM phi (Free fa) = phi (fmap (iterM phi) fa)
