haskell - 管道 3.0 : non linear topologies

Question

我正在查看用于流处理的管道 3.0 包。 The tutorial做得很好也很清楚，除了我无法围绕“压缩和合并”部分。

我的目标是像 ArrowChoice 允许的那样组合管道:

我有一个唯一的制作人要么是一个

我想将第一个管道应用于左值，将另一个管道应用于右值

然后我想合并结果，并继续管道

+----------+                   +------+ - filterLeft ->  pipe1 -> +------------+ 
| producer | - (Either a a) -> | fork |                           | mergeD (?) |
+----------+                   +------+ - filterRight -> pipe2 -> +------------+

我定义 fork就像在教程中:

fork () = 
    runIdentityP . hoist (runIdentityP . hoist runIdentityP) $ forever $ do
        a <- request ()
        lift $ respond a
        lift $ lift $ respond a

oddOrEven x = if odd x then Left x else Right x
producer = fromListS [1..0] >-> mapD oddOrEven
isLeft (Left _) = True
isLeft (Right _) = False
isRight = not . isLeft
filterLeft = filterD isLeft
filterRight = filterD isRight
pipe1 = mapD (\x -> ("seen on left", x))
pipe2 = mapD (\x -> ("seen on right", x))

p1 = producer >-> fork    

问题是我无法使类型正确。本教程似乎只展示了如何将内部(提升的)管道链作为自包含 session 运行，但我希望能够将其值重新注入(inject)管道，而不仅仅是对它们应用效果。我当然试图遵循这些类型，但它们很快就会变得有点毛茸茸的。

有人可以帮我吗？提前致谢。

(PS:这种拓扑的一个例子将是本教程的一个很好的补充，或者甚至更好地介绍如何使用管道模拟 Control.Arrow 东西的部分)

Answer 1

pipe抽象不支持菱形拓扑或任何形式的 Arrow - 样的行为。这不是 API 问题，而是这种情况没有正确或明确定义的行为。

为了解释原因，请允许我将您的图表简化为以下图表:

          +----+
          | pL |
+----+ => +----+ => +----+
| p1 |              | p2 |
+----+ => +----+ => +----+
          | pR |
          +----+

想象一下我们在 p1管道和我们 respond至 pL .如果您还记得教程，代理法要求每个 respond阻塞直到上游。这意味着 p1直到 pL 才能重新获得控制权 request又是。所以在这一点上我们有:

p1阻塞等待 request来自 pL

但是，假设 pL不 request而是 respond s 具有自己的值到 p2 .所以现在我们有:

p1阻塞等待 request来自 pL

pL阻塞等待 request来自 p2

现在假设 p2相反 request来自 pR .代理法说 p2直到 pR 才能重新获得控制权 respond又是。现在我们有:

p1阻塞等待 request来自 pL

pL阻塞等待 request来自 p2

p2阻塞等待 respond来自 pR

现在当 pR 时会发生什么 request s 来自 p1 的值?如果我们查阅我们的区块列表， p1仍然阻塞等待 request来自 pL ，所以没办法收到 request来自 pR . “打结”没有正确的方法，可以这么说，即使 pL和 pR共享同一个 request签名。

更一般地说，代理法确保以下两个不变量:

事件管道的每个管道“上游”将在 respond 上被阻塞。

事件管道“下游”的每个管道都将在 request 上被阻塞。

循环或菱形打破了这些不变量。这就是为什么本教程非常简短地顺便说一下循环拓扑没有“意义”的原因。

在我刚刚给你的例子中，你可以看到为什么钻石会打破这个不变量。当 p1控制它在 pR 的上游，这意味着 pR在 request 上被阻止.然而，当 p2在 pR 的下游获得控制权，这意味着 pR在 respond 上被阻止.这会导致矛盾，因为 pR由于控制流过 pL，所以还没有改变而不是 pR前往 p2 .

机器

因此，您的问题有两种解决方案。一种解决方案是将所需的拆分行为内联到单个管道中。您定义了一个 pE结合了 pL 行为的管道和 pR成一个单一的管道。

这个问题的更优雅的解决方案是爱德华的 machines 风格的东西。 .您定义了一个更受限制的抽象，其功能不如支持 ArrowChoice 的代理强大。 ，你在那个抽象的领域内做你的箭头式的东西，然后当你完成后你将它升级到代理。

如果你眯着眼睛，你可以假装在 Haskell 中有一类当前可用的协程抽象是偏序的。协程抽象是对象，以及来自协程抽象的箭头 C1到协程抽象 C2意味着您可以嵌入 C1 类型的协程在 C2 类型的协程中(即 C1 是 C2 的不正确子集)。

在这个偏序中，代理可能是终端对象，这意味着您可以将代理视为 协程汇编语言 .类似于汇编语言，代理提供的保证较少，但您可以在代理中嵌入更多限制性的协程抽象(即高级语言)。这些高级语言提供了更大的限制，可以实现更强大的抽象(即 Arrow 实例)。

如果您想要一个简单的示例，请考虑最简单的协程抽象之一:Kleisli 箭头:

newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }

instance Category (Kleisli m) where
    id = Kleisli return
    (Kleisli f) . (Kleisli g) = Kleisli (f <=< g)

Kleisli 箭头肯定比代理更具限制性，但由于这种限制，它们支持 Arrow实例。因此，无论何时您需要 Arrow例如，您使用 Kleisli 箭头编写代码，然后使用 Arrow 将其组合起来。表示法，然后当你完成后，你可以使用 mapMD 将该更高级别的 Kleisli 代码“编译”为代理汇编代码。 :

kleisliToProxy :: (Proxy p) => Kleisli m a b -> () -> Pipe p a b m r
kleisliToProxy (Kleisli f) = mapMD f

此编译遵循仿函数定律:

kleisliToProxy id = idT

kleisliToProxy (f . g) = kleisliToProxy f <-< kleisliToProxy g

所以如果你的分支代码可以写成 Kleisli箭头，然后使用 Kleisli代码的那部分的箭头，然后在完成后将其编译为代理。使用这个技巧，您可以将多个协程抽象编译为代理抽象以混合它们。