8

次のような無限の構造があります ( streamsパッケージのStreamタイプを使用):

data U x = U (Stream x) x (Stream x) deriving (Functor,Foldable)

次のように、Traversable のインスタンスを提供したいと考えています。

instance Traversable U where
    traverse f (U lstream focus rstream) = 
        let pairs =  liftA unzip 
                   . sequenceA . fmap (traversepair f) 
                   $ zip lstream rstream 
            traversepair f (a,b) = (,) <$> f a <*> f b
            rebuild c (u,v) = U u c v
        in rebuild <$> f focus <*> pairs

Data.Traversableのドキュメントには、「左から右にトラバースできるデータ構造のクラス」を表すと書かれています。しかし、私の定義は左から右にトラバースするのではなく、外側にトラバースします。Randモナドを含むシーケンス操作の後で両側の値を遅延抽出できるように、そのように定義する必要がありました。

それにもかかわらず、それは有効な定義ですか? Traversable の Typeclassopedia エントリには、「左から右」については何も書かれておらず、「2 つのファンクターの交換」についてのみ言及されていることに気付きました。

4

1 に答える 1

10

このスレッドによると、法律は次のようになります。

  1. traverse Identity == Identity
  2. traverse (Compose . fmap g . f) == Compose . fmap (traverse g) . traverse f

これら 2 つの法則により、トラバースされる構造内の各要素が 1 回だけトラバースされることが保証されます。順番は問いません。Traversableインスタンスは、その特定のデータ型の左から右への意味を定義するとさえ言えます。

ドキュメントには他に 2 つの要件があります。

  • Functorインスタンスでfmapは、恒等アプリカティブ ファンクター ( ) を使用したトラバーサルと同等である必要がありますfmapDefault。
  • FoldableインスタンスでfoldMapは、定数アプリカティブ ファンクター ( ) を使用したトラバーサルと同等である必要がありますfoldMapDefault。

Foldable上記のコードでは、インスタンスとは異なる順序で要素にアクセスする を派生させているため、2 番目の要件を破っていTraversableます。独自のインスタンスを作成しFoldableてfoldMapDefault修正します。

ちなみにsequenceA . fmap (traversepair f)ですtraverse (traversepair f)。

于 2013-01-01T14:01:09.233 に答える