foldFree 和 iterM 如何工作

有一些函数可以帮助拆除 Free 计算，将它们解释为另一个 monad m：iterM :: (Functor f, Monad m) => (f (m a) -> m a) -> (Free f a -> m a) 和 foldFree::Monad m => (forall x. f x -> m x) -> (Free f a -> m a)。他们在做什么？

首先让我们看看如何手动将 Teletype a 函数解释为 IO。我们可以看到 Free f a 被定义了

data Free f a 
    = Pure a 
    | Free (f (Free f a))

Pure 案例很简单：

interpretTeletype::Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = _

现在，如何解释用 Free 构造函数构建的 Teletype 计算？我们想通过检查 teletypeF::TeletypeF (Teletype a) 来得到 IO a 的值。首先，我们将编写一个函数 runIO::TeletypeF a -> IO a，它将单个自由 monad 层映射到 IO 动作：

runIO::TeletypeF a -> IO a
runIO (PrintLine msg x) = putStrLn msg *> return x
runIO (ReadLine k) = fmap k getLine

现在我们可以用 runIO 来填补 interpretTeletype 的其余部分。回想一下 teletypeF::TeletypeF (Teletype a) 是 TeletypeF 仿函数的一层，它包含了 Free 计算的其余部分。我们将使用 runIO 来解释最外层（所以我们有 runIO teletypeF::IO (Teletype a)）然后使用 IO monad 的 >>= 组合来解释返回的 Teletype a。

interpretTeletype::Teletype a -> IO a
interpretTeletype (Pure x) = return x
interpretTeletype (Free teletypeF) = runIO teletypeF >>= interpretTeletype

foldFree 的定义只是 interpretTeletype 的定义，除了 runIO 函数已被考虑在内。因此，foldFree 独立于任何特定的基础仿函数和任何目标 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 的等级为 2：eta 是一种自然变形。我们本来可以给 foldFree 一种 Monad m => (f (Free f a) -> m (Free f a)) -> Free f a -> m a，但是这样可以让 eta 自由地检查 f 层内的 Free 计算。赋予 foldFree 这种更具限制性的类型可确保 eta 一次只能处理单个层。

iterM 确实赋予折叠功能检查子计算的能力。上一次迭代的（monadic）结果可用于 f 的参数中的下一个。iterM 类似于一个 paramorphism， 而 foldFree 就像一个 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)