**Packages**- base

Class of data structures that can be traversed from left to right, performing an action on each element.
See also
* *Applicative Programming with Effects*, by Conor McBride and Ross Paterson, online at http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
* *The Essence of the Iterator Pattern*, by Jeremy Gibbons and Bruno Oliveira, in *Mathematically-Structured Functional Programming*, 2006, and online at http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator.
Note that the functions mapM and sequence generalize Prelude functions of the same names from lists to any Traversable functor. To avoid ambiguity, either import the Prelude hiding these names or qualify uses of these function names with an alias for this module.

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).