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)
```