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)