haskell - Haskell的FreeT和Coroutine类型有什么关系

Question

在Monad.Reader Issue 19中的“协程管道”文章中，作者定义了一个通用的Coroutine类型:

newtype Coroutine f m a = Coroutine
  { resume :: m (Either (f (Coroutine f m a)) a)
  }

我注意到这种类型与 FreeT 非常相似输入 free封装:

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

newtype FreeT f m a = FreeT
  { runFreeT :: m (FreeF f a (FreeT f m a))
  }

看来FreeT和Coroutine是同构的。以下是从一个函数到另一个函数的映射:

freeTToCoroutine
  :: forall f m a. (Functor f, Functor m) => FreeT f m a -> Coroutine f m a
freeTToCoroutine (FreeT action) = Coroutine $ fmap f action
  where
    f :: FreeF f a (FreeT f m a) -> Either (f (Coroutine f m a)) a
    f (Pure a) = Right a
    f (Free inner) = Left $ fmap freeTToCoroutine inner

coroutineToFreeT
  :: forall f m a. (Functor f, Functor m) => Coroutine f m a -> FreeT f m a
coroutineToFreeT (Coroutine action) = FreeT $ fmap f action
  where
    f :: Either (f (Coroutine f m a)) a -> FreeF f a (FreeT f m a)
    f (Right a) = Pure a
    f (Left inner) = Free $ fmap coroutineToFreeT inner

我有以下问题:

1. FreeT 和 Coroutine 类型之间有什么关系？为什么《Coroutine Pipelines》的作者不使用 FreeT 类型，而是创建 Coroutine 类型？
2. 自由单子(monad)和协程之间是否存在某种更深层次的关系？类型同构似乎并不是巧合。

3. 为什么 Haskell 中流行的流媒体库不基于 FreeT？

   pipes中的核心数据类型是 Proxy :

   data Proxy a' a b' b m r
     = Request a' (a  -> Proxy a' a b' b m r )
     | Respond b  (b' -> Proxy a' a b' b m r )
     | M          (m    (Proxy a' a b' b m r))
     | Pure    r
   

   conduit中的核心数据类型是 Pipe :

   data Pipe l i o u m r
     = HaveOutput (Pipe l i o u m r) (m ()) o
     | NeedInput (i -> Pipe l i o u m r) (u -> Pipe l i o u m r)
     | Done r
     | PipeM (m (Pipe l i o u m r))
     | Leftover (Pipe l i o u m r) l
   

   我想可以基于FreeT编写Proxy或Pipe数据类型，所以我想知道为什么它没有完成？是出于性能原因吗？

   我在流行的流媒体库中看到的 FreeT 的唯一提示是 pipes-group ，它使用 FreeT 对流中的项目进行分组。

Answer 1

为了回答你的第二个问题，我们首先通过查看 Free 来简化问题。 。 Free f a允许您构建 f a 的形状 AST - 稍后减少的值(又名解释)。在将文章中的 monad 转换器与未提升的自由结构进行比较时，我们可以简单地选择 Identity对于 m ，这是从变压器构造基本单子(monad)的通常做法:Free f = FreeT Identity f .

Monad Reader 文章首先介绍了一个提升的 Trampoline monad 变压器，所以让我们首先看看未提升的版本，其中 Identity省略:

data Trampoline a = Return a | Bounce (Trampoline a)

如果我们将其与 Free 进行比较

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

稍微眯一下眼睛，我们可以看到我们真正需要做的就是“删除” f -结构，就像我们之前“删除”m一样-结构。所以，我们有Trampoline = Free Identity ，又因为Identity没有结构。反过来，这意味着这个蹦床是 FreeT Identity Identity :一种简陋的协程，形状平凡，无法使用效果来确定是弹跳还是返回。这就是这个蹦床和蹦床单子(monad)变压器之间的区别:变压器允许反弹与 m 交错。 - 行动。

通过一些工作，我们还可以看到生成器和消费者是针对f的特定选择的免费单子(monad)。 ，分别((,) a)和((->) a) 。他们的免费 monad 转换器版本同样允许它们交错 m - Action (例如，生成器可以在产生之前要求用户输入)。 Coroutine概括两者f 、AST 形状(对于 Trampoline，固定为 f ~ Identity)以及 m ~ Identity 可以交错的效果类型(固定为无效果，或 Free )。 。这正是FreeT m f .

直观地说，如果 Free f是纯粹构造 f 的 monad形 AST 然后 FreeT m f是用于构建 f 的 monad形状 AST 与 m 提供的效果交错。如果你仔细观察一下，就会发现这正是协程:一种完整的泛化，它对构造的 AST 的形状和用于构造它的效果类型进行参数化的具体化计算。