8

我有一个像下面这样的无限结构（使用流包中的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 monad的序列操作之后能够在两侧延迟提取值。

它仍然是一个有效的定义吗？我注意到Traversable 的 Typeclassopedia 条目没有说任何关于“从左到右”的内容，它只讨论了“交换两个函子”。

4

1 回答 1

10

根据这个线程，法律应该是：

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

这两条定律确保遍历结构中的每个元素都被遍历一次。以哪个顺序无关紧要。您甚至可以说一个Traversable实例定义了从左到右对于该特定数据类型的含义。

文档中还有另外两个要求：

  • 在这种Functor情况下，fmap应该等价于使用身份应用函子 ( fmapDefault) 进行遍历。
  • 在该Foldable实例中，foldMap应该等效于使用常量应用函子 ( foldMapDefault) 进行遍历。

在上面的代码中，您打破了第二个要求，因为您正在派生Foldable，它将以与您的Traversable实例不同的顺序访问元素。Foldable为foldMapDefault修复该问题创建您自己的实例。

顺便说一句，sequenceA . fmap (traversepair f)是traverse (traversepair f)。

于 2013-01-01T14:01:09.233 回答