Do traverses really require passing from left to right?

Question

I have an infinite structure similar to the following (using Stream type streams ):

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

I want to provide a Traversable instance for it, for example:

 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) = (,) <$> fa <*> fb rebuild c (u,v) = U ucv in rebuild <$> f focus <*> pairs 

The documentation for Data.Traversable says they are "a class of data structures that can be traversed from left to right." But my definition does not pass from left to right, it passes out. I had to define it in such a way as to lazily extract values ​​from both sides after the sequence operation using Rand monad.

Is this the correct definition? I noticed that the Typeclassopedia entry for Traversable does not say anything about “from left to right,” it only talks about “switching two functors”.

Answer 1

According to this stream, laws should be:

• traverse Identity == Identity
• traverse (Compose . fmap g . f) == Compose . fmap (traverse g) . traverse f

These 2 laws guarantee that each element in the crossed structure passes exactly once. It doesn't matter in what order. You can even say that the Traversable instance defines what “left to right” means for this particular data type.

There are two more requirements in the documentation:

• In a Functor instance, fmap should be equivalent to crawling with an identical application functor ( fmapDefault ).
• In an instance of Foldable foldMap should be equivalent to a crawl with a persistent applicative functor ( foldMapDefault ).

In the code above, you violate the second requirement because you get a Foldable that will visit elements in a different order than your Traversable instance. Create your own instance for Foldable using foldMapDefault hotfixes.

By the way, sequenceA . fmap (traversepair f) sequenceA . fmap (traversepair f) is traverse (traversepair f) .