Functors representing data structures that can be traversed from left to right.
Minimal complete definition: traverse or sequenceA.
Instances are similar to Functor, e.g. given a data type
> data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
> instance Traversable Tree
> traverse f Empty = pure Empty
> traverse f (Leaf x) = Leaf <$> f x
> traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
This is suitable even for abstract types, as the laws for <*> imply a form of associativity.
The superclass instances should satisfy the following:
* In the Functor instance, fmap should be equivalent to traversal with the identity applicative functor (fmapDefault).
* In the Foldable instance, Data.Foldable.foldMap should be equivalent to traversal with a constant applicative functor (foldMapDefault).