Traversables真的需要"从左到右"遍历吗？

Question

我有一个无限的结构,如下所示(使用流包中的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的文档说它们代表了"可以从左到右遍历的数据结构类".但是我的定义不是从左到右遍历,而是向外遍历.我不得不把它定义这种方式是能够在后懒洋洋地提取双方值序列涉及操作兰德单子.

这是一个有效的定义吗？我注意到Traversable的Typeclassopedia条目没有说"从左到右",它只谈到"通勤两个仿函数".

Answer 1

根据这个线程,法律应该是:

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

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

文档中还有两个其他要求:

• 在Functor实例中,fmap应该等同于使用identity applicative functor(fmapDefault)进行遍历.
• 在Foldable实例中,foldMap应该等效于使用常量applicative functor(foldMapDefault)遍历.

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

顺便说一下,sequenceA . fmap (traversepair f)是traverse (traversepair f).