13

我正在查看用于流处理的管道 3.0 包。这个教程做得很好而且很清楚，除了我不能把头绕在“压缩和合并”部分。

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

  • 我有一个独特的 Either aa 制作人
  • 我想将第一个管道应用于左值，另一个应用于右值
  • 然后我想合并结果，并继续管道


+----------+                   +------+ - 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

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

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

（PS：这种拓扑结构的示例将是对教程的一个很好的补充，或者甚至是关于如何Control.Arrow使用管道模拟这些东西的更好的部分）

4

1 回答 1

15

该pipe抽象不支持菱形拓扑或任何形式的类似Arrow行为。这不是 API 问题，而是这种场景没有正确或明确定义的行为。

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

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

想象一下，我们在p1管道上，我们respond到pL。如果您还记得教程，代理法要求每个respond阻塞直到上游。这意味着p1直到再次 s 才能重新获得控制权pL request。所以此时我们有：

  • p1阻塞等待request来自pL

但是，假设它还pL没有request，而是responds 具有自己的值 to p2。所以现在我们有：

  • p1阻塞等待request来自pL
  • pL阻塞等待request来自p2

现在假设p2srequest来自pR。代理法规定，p2直到pR responds 再次获得控制权。现在我们有：

  • p1阻塞等待request来自pL
  • pL阻塞等待request来自p2
  • p2阻塞等待respond来自pR

现在当pR requestsa 值来自时会发生什么p1？如果我们查看我们的块列表，p1仍然被阻塞等待requestfrom pL，因此它无法接收requestfrom pR。pL可以说，即使和pR共享相同的request签名，也没有正确的方法来“打结” 。

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

  • 活动管道“上游”的每个管道都将被阻塞respond
  • 活动管道“下游”的每个管道都将被阻塞request

循环或菱形打破了这些不变量。这就是为什么教程非常简短地指出循环拓扑没有“意义”。

你可以在我刚刚给你的例子中看到为什么钻石会破坏这个不变量。当p1有控制权时，它位于 的上游pR，这意味着pR被阻止在request. 但是，当p2获得控制权时，它位于 的下游pR，这意味着pR在respond. 这导致了一个矛盾，因为pR自从控制流过pL并且没有pR到达p2.

机器

因此，您的问题有两种解决方案。一种解决方案是将您想要的拆分行为内联到单个管道中。您定义一个将和pE的行为组合到单个管道中的管道。pLpR

这个问题的更优雅的解决方案是 Edward 的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符号组合它，然后当您完成后，您可以使用以下命令将更高级别的 Kleisli 代码“编译”为代理汇编代码mapMD：

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箭头，然后在完成后将其编译为代理。使用这个技巧，您可以将多个协程抽象编译为代理抽象来混合它们。

于 2013-01-07T18:45:01.867 回答