Do Traversables really require to be traversed "left-to-right"?

Question

I have an infinite structure like the following (using the Stream type from the streams package):

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

I want to provide an instance of Traversable for it, like this:

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

The documentation for Data.Traversable says that they represent the "class of data structures that can be traversed from left to right". But my definition does not traverse from left to right, it traverses outwardly. I had to define it that way to be able to lazily extract values on both sides after a sequence operation involving the Rand monad.

Is it a valid definition nonetheless? I have noticed that the Typeclassopedia entry for Traversable doesn't say anything about "left-to-right", it only talks about "commuting two functors".

Answer 1

According to this thread the laws should be:

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

These 2 laws ensure that each element in the traversed structure is traversed exactly once. It does not matter in which order. You could even say that a Traversable instance defines what left-to-right means for that particular datatype.

There are two other requirements in the documentation:

• In the Functor instance, fmap should be equivalent to traversal with the identity applicative functor (fmapDefault).
• In the Foldable instance, foldMap should be equivalent to traversal with a constant applicative functor (foldMapDefault).

In your above code, you break the second requirement, because you're deriving Foldable, which will visit the elements in a different order than your Traversable instance. Creating your own instance for Foldable with foldMapDefault fixes that.

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