13

ストリーム処理用のパイプ 3.0 パッケージを見ています。チュートリアルは非常によくできており、非常に明確ですが、「zip とマージ」セクションに頭を悩ませることはできません。

私の目標は、ArrowChoice のようにパイプを組み合わせることです。

  • 私はどちらかの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ブロックが上流までブロックされる必要があります。つまり、再び sp1まで制御を取り戻すことはできませんpL request。したがって、この時点で次のことがわかります。

  • p1送信者を待ってブロックされましrequestたpL

ただし、それpLはrequestまだではなく、代わりにrespond独自の値 to を持っているとしp2ます。これで、次のようになりました。

  • p1送信者を待ってブロックされましrequestたpL
  • pL送信者を待ってブロックされましrequestたp2

ここで、p2代わりにrequestが fromであるとしpRます。代理の法則では、再び sp2まで制御を取り戻すことはできないとされていpR respondます。これで、次のようになりました。

  • p1送信者を待ってブロックされましrequestたpL
  • pL送信者を待ってブロックされましrequestたp2
  • p2送信者を待ってブロックされましrespondたpR

pR requestから値を取得するとどうなりp1ますか? ブロックのリストを調べてみると、p1はまだ from を待っている状態でブロックされているため、requestfrompLを受け取るにはrequest適していませんpR。と が同じ署名pLをpR共有していたとしても、いわば「結び目を結ぶ」正しい方法はありません。request

より一般的には、代理法則は次の 2 つの不変条件を保証します。

  • アクティブなパイプの「上流」にあるすべてのパイプは、respond
  • アクティブなパイプの「下流」のすべてのパイプは、request

サイクルまたはダイアモンドは、これらの不変条件を破ります。これが、循環トポロジーが「意味を成さない」ことをチュートリアルで非常に簡単に述べている理由です。

先ほど示した例で、ダイヤモンドがこの不変条件を破る理由がわかります。p1制御が の上流にあった場合、 でブロックされたpRことを意味します。ただし、制御を取得したときは の下流にありました。これは、 でブロックされたことを意味します。これは矛盾につながります。なぜなら、制御が流れて に到達しないため、まだ変更できていないからです。pRrequestp2pRpRrespondpRpLpRp2

機械

したがって、問題には2つの解決策があります。1 つの解決策は、目的の分割動作を 1 つのパイプにインライン化することです。とpEの動作を 1 つのパイプに結合するパイプを定義します。pLpR

この問題に対するより洗練された解決策は、エドワードのスタイルの何かですmachines。をサポートするプロキシよりも強力ではない、より制限された抽象化を定義しArrowChoice、その抽象化のドメイン内で矢印のようなことを行い、完了したらプロキシにアップグレードします。

目を細めると、Haskell で現在利用可能なコルーチン抽象化のカテゴリが半順序であるふりをすることができます。コルーチンの抽象化はオブジェクトであり、コルーチンの抽象化からコルーチンの抽象化への矢印はC1、型のコルーチンC2に型のコルーチンを埋め込むことができることを意味します(つまり、 は の不適切なサブセットです)。C1C2C1C2

この部分的な順序では、プロキシはおそらくターミナル オブジェクトです。つまり、プロキシはコルーチンのアセンブリ言語と考えることができます。アセンブリ言語のアナロジーに従うと、プロキシは提供する保証が少なくなりますが、より限定的なコルーチンの抽象化 (つまり、高レベル言語) をプロキシ内に埋め込むことができます。これらの高水準言語は、より強力な抽象化 (つまりArrowインスタンス) を可能にするより大きな制限を提供します。

この簡単な例が必要な場合は、最も単純なコルーチンの抽象化の 1 つである 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 に答える