管道3.0:非线性拓扑

Question

我正在看一下用于流处理的管道3.0包.该教程非常好,非常清楚,除了我无法绕过"zip和merge"部分.

我的目标是结合管道有点像ArrowChoice允许做:

• 我有一个独特的生产者Aither aa
• 我想将第一个管道应用于Left值,将另一个管道应用于Right值
• 然后我想合并结果,并继续管道

+----------+                   +------+ - 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使用管道来模拟这些东西)

Answer 1

该pipe抽象不支持钻石拓扑或任何形式的Arrow样行为.这不是API问题,而是针对此类方案没有正确或明确定义的行为.

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

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

想象一下,我们正处于p1管道中,而我们正处于管道respond中pL.如果您还记得本教程,则代理法则要求每个respond块直到上游.这意味着再次p1无法重新获得控制权pL request.所以在这一点上我们有:

• p1阻止等待request来自pL

但是,假设pL还没有request,而是respond使用自己的值p2.所以现在我们有:

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

现在假设p2相反request来自pR.代理法律规定,p2再也不能重新获得控制权pR respond.现在我们有:

• 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管道,该管道将行为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符号将其组合,然后在完成后,您可以使用以下命令将更高级别的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在代码的该部分使用箭头,然后在完成后将其编译为代理.使用这个技巧,您可以将多个协同程序抽象编译到代理抽象中以混合它们.