-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Uniplate-style generic traversals for fixed-point types, with some extras.
--   
--   Uniplate-style generic traversals for fixed-point types, which can be
--   optionally annotated with attributes. We also provide a generic
--   zipper. See the module <a>Data.Generics.Fixplate</a> and then the
--   individual modules for more detailed information.
@package fixplate
@version 0.1.2


-- | The core types of Fixplate.
module Data.Generics.Fixplate.Base

-- | The attribute of the root node.
attribute :: Attr f a -> a

-- | A function forgetting all the attributes from an annotated tree.
forget :: Functor f => Attr f a -> Mu f

-- | The fixed-point type.
newtype Mu f
Fix :: f (Mu f) -> Mu f
unFix :: Mu f -> f (Mu f)

-- | Annotations.
data Ann f a b
Ann :: a -> f b -> Ann f a b
attr :: Ann f a b -> a
unAnn :: Ann f a b -> f b

-- | Annotated fixed-point type.
type Attr f a = Mu (Ann f a)

-- | "Functorised" versions of standard type classes. If you have your a
--   structure functor, for example
--   
--   <pre>
--   Expr e 
--     = Kst Int 
--     | Var String 
--     | Add e e 
--     deriving (Eq,Ord,Read,Show,Functor,Foldable,Traversable)
--   </pre>
--   
--   you should make it an instance of these, so that the fixed-point type
--   <tt>Mu Expr</tt> can be an instance of <tt>Eq</tt>, <tt>Ord</tt> and
--   <tt>Show</tt>. Doing so is very easy:
--   
--   <pre>
--   instance EqF   Expr where equalF     = (==)
--   instance OrdF  Expr where compareF   = compare
--   instance ShowF Expr where showsPrecF = showsPrec
--   </pre>
--   
--   The <tt>Read</tt> instance depends on whether we are using GHC or not.
--   The Haskell98 version is
--   
--   <pre>
--   instance ReadF Expr where readsPrecF = readsPrec
--   </pre>
--   
--   while the GHC version is
--   
--   <pre>
--   instance ReadF Expr where readPrecF  = readPrec
--   </pre>
class EqF f
equalF :: (EqF f, Eq a) => f a -> f a -> Bool
class EqF f => OrdF f
compareF :: (OrdF f, Ord a) => f a -> f a -> Ordering
class ShowF f
showsPrecF :: (ShowF f, Show a) => Int -> f a -> ShowS
class ReadF f
readPrecF :: (ReadF f, Read a) => ReadPrec (f a)

-- | A newtype wrapper around <tt>Attr f a</tt> so that we can make
--   <tt>Attr f</tt> an instance of Functor, Foldable and Traversable. This
--   is necessary since Haskell does not allow partial application of type
--   synonyms.
newtype Attrib f a
Attrib :: Attr f a -> Attrib f a
unAttrib :: Attrib f a -> Attr f a
instance Traversable f => Traversable (Attrib f)
instance Foldable f => Foldable (Attrib f)
instance Functor f => Functor (Attrib f)
instance (ShowF f, Show a) => Show (Attrib f a)
instance Traversable f => Traversable (Ann f a)
instance Foldable f => Foldable (Ann f a)
instance Functor f => Functor (Ann f a)
instance (Read a, ReadF f) => ReadF (Ann f a)
instance (Show a, ShowF f) => ShowF (Ann f a)
instance (Ord a, OrdF f) => OrdF (Ann f a)
instance (Eq a, EqF f) => EqF (Ann f a)
instance ReadF f => Read (Mu f)
instance ShowF f => Show (Mu f)
instance OrdF f => Ord (Mu f)
instance EqF f => Eq (Mu f)


-- | Scary named folds...
module Data.Generics.Fixplate.Morphisms

-- | A <i>paramorphism</i> is a generalized (right) fold.
para :: Functor f => (Mu f -> f a -> a) -> Mu f -> a
para' :: Functor f => (f (Mu f, a) -> a) -> Mu f -> a
paraList :: (Functor f, Foldable f) => (Mu f -> [a] -> a) -> Mu f -> a

-- | A <i>catamorphism</i> is a simpler version of a paramorphism
cata :: Functor f => (f a -> a) -> Mu f -> a

-- | An <i>anamorphism</i> is simply an unfold.
ana :: Functor f => (a -> f a) -> a -> Mu f

-- | A <i>hylomorphism</i> is the composition of a catamorphism and an
--   anamorphism.
hylo :: Functor f => (f a -> a) -> (b -> f b) -> (b -> a)


-- | "Open" functions, working on functors instead of trees.
module Data.Generics.Fixplate.Open

-- | List of elements of a structure.
toList :: Foldable t => t a -> [a]

-- | The <a>mapAccumL</a> function behaves like a combination of
--   <a>fmap</a> and <a>foldl</a>; it applies a function to each element of
--   a structure, passing an accumulating parameter from left to right, and
--   returning a final value of this accumulator together with the new
--   structure.
mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)

-- | The <a>mapAccumR</a> function behaves like a combination of
--   <a>fmap</a> and <tt>foldr</tt>; it applies a function to each element
--   of a structure, passing an accumulating parameter from right to left,
--   and returning a final value of this accumulator together with the new
--   structure.
mapAccumR :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL_ :: Traversable f => (a -> b -> (a, c)) -> a -> f b -> f c
mapAccumR_ :: Traversable f => (a -> b -> (a, c)) -> a -> f b -> f c

-- | The children together with functions replacing that particular child.
holes :: Traversable f => f a -> f (a, a -> f a)
holesList :: Traversable f => f a -> [(a, a -> f a)]

-- | Apply the given function to each child in turn.
apply :: Traversable f => (a -> a) -> f a -> f (f a)

-- | Builds up a structure from a list of the children. It is unsafe in the
--   sense that it will throw an exception if there are not enough elements
--   in the list.
builder :: Traversable f => f a -> [b] -> f b

-- | Extracts the ith child.
project :: Foldable f => Int -> f a -> Maybe a
unsafeProject :: Foldable f => Int -> f a -> a

-- | Number of children. This is the generalization of <a>length</a> to
--   foldable functors:
--   
--   <pre>
--   sizeF x = length (toList x)
--   </pre>
sizeF :: Foldable f => f a -> Int

-- | Enumerates children from the left to the right, starting with zero.
--   Also returns the number of children. This is just a simple application
--   of <a>mapAccumL</a>.
enumerate :: Traversable f => f a -> (Int, f (Int, a))
enumerateWith :: Traversable f => (Int -> a -> b) -> f a -> (Int, f b)
enumerateWith_ :: Traversable f => (Int -> a -> b) -> f a -> f b

-- | A type encoding the "shape" of the functor data: We ignore all the
--   fields whose type is the parameter type, but remember the rest:
--   
--   <pre>
--   newtype Shape f = Shape { unShape :: f () }
--   </pre>
--   
--   This can be used to decide whether two realizations are compatible.
data Shape f

-- | Extracting the "shape" of the functor
shape :: Functor f => f a -> Shape f

-- | Zips two structures if they are compatible.
zipF :: (Traversable f, EqF f) => f a -> f b -> Maybe (f (a, b))
unzipF :: Functor f => f (a, b) -> (f a, f b)

-- | Zipping two structures using a function.
zipWithF :: (Traversable f, EqF f) => (a -> b -> c) -> f a -> f b -> Maybe (f c)

-- | Unsafe version of <a>zipWithF</a>: does not check if the two
--   structures are compatible. It is left-biased in the sense that the
--   structure of the second argument is retained.
unsafeZipWithF :: Traversable f => (a -> b -> c) -> f a -> f b -> f c

-- | Monadic version of <a>zipWithF</a>. TODO: better name?
zipWithFM :: (Traversable f, EqF f, Monad m) => (a -> b -> m c) -> f a -> f b -> m (Maybe (f c))
unsafeZipWithFM :: (Traversable f, Monad m) => (a -> b -> m c) -> f a -> f b -> m (f c)
instance ShowF f => Show (Shape f)
instance OrdF f => Ord (Shape f)
instance EqF f => Eq (Shape f)


-- | Uniplate-style traversals.
module Data.Generics.Fixplate.Traversals

-- | The list of direct descendants.
children :: Foldable f => Mu f -> [Mu f]

-- | The list of all substructures. Together with list-comprehension syntax
--   this is a powerful query tool. For example the following is how you
--   get the list of all variable names in an expression:
--   
--   <pre>
--   variables expr = [ s | Fix (Var s) &lt;- universe expr ]
--   </pre>
universe :: Foldable f => Mu f -> [Mu f]

-- | Bottom-up transformation.
transform :: Functor f => (Mu f -> Mu f) -> Mu f -> Mu f
transformM :: (Traversable f, Monad m) => (Mu f -> m (Mu f)) -> Mu f -> m (Mu f)

-- | Top-down transformation. This provided only for completeness; usually,
--   it is <a>transform</a> what you want use instead.
topDownTransform :: Functor f => (Mu f -> Mu f) -> Mu f -> Mu f
topDownTransformM :: (Traversable f, Monad m) => (Mu f -> m (Mu f)) -> Mu f -> m (Mu f)

-- | Non-recursive top-down transformation.
descend :: Functor f => (Mu f -> Mu f) -> Mu f -> Mu f
descendM :: (Traversable f, Monad m) => (Mu f -> m (Mu f)) -> Mu f -> m (Mu f)

-- | Bottom-up transformation until a normal form is reached.
rewrite :: Functor f => (Mu f -> Maybe (Mu f)) -> Mu f -> Mu f
rewriteM :: (Traversable f, Monad m) => (Mu f -> m (Maybe (Mu f))) -> Mu f -> m (Mu f)

-- | We <i>annotate</i> the nodes of the tree with functions which replace
--   that particular subtree.
context :: Traversable f => Mu f -> Attr f (Mu f -> Mu f)

-- | Flattened version of <a>context</a>.
contextList :: Traversable f => Mu f -> [(Mu f, Mu f -> Mu f)]

-- | (Strict) left fold. Since <tt>Mu f</tt> is not a functor, but a data
--   type, we cannot make it an instance of the <tt>Foldable</tt> type
--   class.
foldLeft :: Foldable f => (a -> Mu f -> a) -> a -> Mu f -> a
foldLeftLazy :: Foldable f => (a -> Mu f -> a) -> a -> Mu f -> a
foldRight :: Foldable f => (Mu f -> a -> a) -> a -> Mu f -> a


-- | Synthetising attributes, partly motivated by Attribute Grammars.
module Data.Generics.Fixplate.Attributes

-- | A newtype wrapper around <tt>Attr f a</tt> so that we can make
--   <tt>Attr f</tt> an instance of Functor, Foldable and Traversable. This
--   is necessary since Haskell does not allow partial application of type
--   synonyms.
newtype Attrib f a
Attrib :: Attr f a -> Attrib f a
unAttrib :: Attrib f a -> Attr f a

-- | Map over annotations
--   
--   <pre>
--   annMap f = unAttrib . fmap f . Attrib
--   </pre>
annMap :: Functor f => (a -> b) -> Attr f a -> Attr f b

-- | <i>Synthetised</i> attributes are created in a bottom-up manner. As an
--   example, the <tt>sizes</tt> function computes the sizes of all
--   subtrees:
--   
--   <pre>
--   sizes :: (Functor f, Foldable f) =&gt; Mu f -&gt; Attr f Int
--   sizes = synthetise (\t -&gt; 1 + sum t)
--   </pre>
--   
--   (note that <tt>sum</tt> here is <tt>Data.Foldable.sum == Prelude.sum .
--   Data.Foldable.toList</tt>)
synthetise :: Functor f => (f a -> a) -> Mu f -> Attr f a

-- | Generalization of <tt>scanr</tt> for trees.
synthetise' :: Functor f => (a -> f b -> b) -> Attr f a -> Attr f b
synthetiseList :: (Functor f, Foldable f) => ([a] -> a) -> Mu f -> Attr f a

-- | Monadic version of <a>synthetise</a>.
synthetiseM :: (Traversable f, Monad m) => (f a -> m a) -> Mu f -> m (Attr f a)

-- | <i>Inherited</i> attributes are created in a top-down manner. As an
--   example, the <tt>depths</tt> function computes the depth (the distance
--   from the root, incremented by 1) of all subtrees:
--   
--   <pre>
--   depths :: Functor f =&gt; Mu f -&gt; Attr f Int
--   depths = inherit (\_ i -&gt; i+1) 0
--   </pre>
inherit :: Functor f => (Mu f -> a -> a) -> a -> Mu f -> Attr f a

-- | Generalization of <tt>scanl</tt> for trees
inherit' :: Functor f => (a -> b -> a) -> a -> Attr f b -> Attr f a

-- | Monadic version of <a>inherit</a>.
inheritM :: (Traversable f, Monad m) => (Mu f -> a -> m a) -> a -> Mu f -> m (Attr f a)
inheritM_ :: (Traversable f, Monad m) => (Mu f -> a -> m a) -> a -> Mu f -> m ()

-- | Monadic top-down "sweep" of a tree. It's kind of a more complicated
--   folding version of <a>inheritM</a>. This is unsafe in the sense that
--   the user is responsible to retain the shape of the node. TODO: better
--   name?
topDownSweepM :: (Traversable f, Monad m) => (f () -> a -> m (f a)) -> a -> Mu f -> m ()

-- | An attributed version of <a>topDownSweepM</a>. Probably more useful.
topDownSweepM' :: (Traversable f, Monad m) => (b -> f b -> a -> m (f a)) -> a -> Attr f b -> m ()

-- | Synthetising attributes via an accumulating map in a left-to-right
--   fashion (the order is the same as in <tt>foldl</tt>).
synthAccumL :: Traversable f => (a -> Mu f -> (a, b)) -> a -> Mu f -> (a, Attr f b)

-- | Synthetising attributes via an accumulating map in a right-to-left
--   fashion (the order is the same as in <tt>foldr</tt>).
synthAccumR :: Traversable f => (a -> Mu f -> (a, b)) -> a -> Mu f -> (a, Attr f b)
synthAccumL_ :: Traversable f => (a -> Mu f -> (a, b)) -> a -> Mu f -> Attr f b
synthAccumR_ :: Traversable f => (a -> Mu f -> (a, b)) -> a -> Mu f -> Attr f b

-- | We use <a>synthAccumL</a> to number the nodes from <tt>0</tt> to
--   <tt>(n-1)</tt> in a left-to-right traversal fashion, where <tt>n ==
--   length (universe tree)</tt> is the number of substructures, which is
--   also returned.
enumerateNodes :: Traversable f => Mu f -> (Int, Attr f Int)
enumerateNodes_ :: Traversable f => Mu f -> Attr f Int

-- | Bottom-up transformations which automatically resynthetise attributes
--   in case of changes.
synthTransform :: Traversable f => (f a -> a) -> (Attr f a -> Maybe (f (Attr f a))) -> Attr f a -> Attr f a

-- | Bottom-up transformations to normal form (applying transformation
--   exhaustively) which automatically resynthetise attributes in case of
--   changes.
synthRewrite :: Traversable f => (f a -> a) -> (Attr f a -> Maybe (f (Attr f a))) -> Attr f a -> Attr f a

-- | Merges two layers of annotations into a single one.
annZip :: Functor f => Mu (Ann (Ann f a) b) -> Attr f (a, b)
annZipWith :: Functor f => (a -> b -> c) -> Mu (Ann (Ann f a) b) -> Attr f c

-- | Merges three layers of annotations into a single one.
annZip3 :: Functor f => Mu (Ann (Ann (Ann f a) b) c) -> Attr f (a, b, c)
annZipWith3 :: Functor f => (a -> b -> c -> d) -> Mu (Ann (Ann (Ann f a) b) c) -> Attr f d


-- | The Zipper is a data structure which maintains a location in a tree,
--   and allows O(1) movement and local changes (to be more precise, in our
--   case it is O(k) where k is the number of children of the node at
--   question; typically this is a very small number).
module Data.Generics.Fixplate.Zipper

-- | A context node.
type Node f = Either (Mu f) (Path f)

-- | The context or path type. The invariant we must respect is that there
--   is exactly one child with the <a>Right</a> constructor.
data Path f
Top :: Path f
Path :: f (Node f) -> Path f
unPath :: Path f -> f (Node f)

-- | The zipper type itself, which encodes a locations in thre tree <tt>Mu
--   f</tt>.
data Loc f
Loc :: Mu f -> Path f -> Loc f
focus :: Loc f -> Mu f
path :: Loc f -> Path f

-- | Creates a zipper from a tree, with the focus at the root.
root :: Mu f -> Loc f

-- | Restores a tree from a zipper.
defocus :: Traversable f => Loc f -> Mu f

-- | We attribute all nodes with a zipper focused at that location.
locations :: Traversable f => Mu f -> Attr f (Loc f)

-- | The list of all locations.
locationsList :: Traversable f => Mu f -> [Loc f]

-- | The zipper version of <a>forget</a>.
locForget :: Functor f => Loc (Ann f a) -> Loc f

-- | Extracts the subtree at focus. Synonym of <a>focus</a>.
extract :: Loc f -> Mu f

-- | Replaces the subtree at focus.
replace :: Mu f -> Loc f -> Loc f

-- | Modifies the subtree at focus.
modify :: (Mu f -> Mu f) -> Loc f -> Loc f

-- | Moves down to the child with the given index. The leftmost children
--   has index <tt>0</tt>.
moveDown :: Traversable f => Int -> Loc f -> Maybe (Loc f)

-- | Moves down to the leftmost child.
moveDownL :: Traversable f => Loc f -> Maybe (Loc f)

-- | Moves down to the rightmost child.
moveDownR :: Traversable f => Loc f -> Maybe (Loc f)

-- | Moves up.
moveUp :: Traversable f => Loc f -> Maybe (Loc f)
moveRight :: Traversable f => Loc f -> Maybe (Loc f)
moveLeft :: Traversable f => Loc f -> Maybe (Loc f)

-- | Checks whether we are at the top (root).
isTop :: Loc f -> Bool

-- | Checks whether we cannot move down.
isBottom :: Traversable f => Loc f -> Bool
isLeftmost :: Traversable f => Loc f -> Bool
isRightmost :: Traversable f => Loc f -> Bool

-- | Gives back the index of the given location among the children of its
--   parent. Indexing starts from zero. In case of root node (no parent),
--   we also return zero.
horizontalPos :: Foldable f => Loc f -> Int

-- | We return the full path from the root as a sequence of child indices.
--   This means that
--   
--   <pre>
--   loc == foldl (flip unsafeMoveDown) (moveTop loc) (fullPathDown loc)
--   </pre>
fullPathDown :: Foldable f => Loc f -> [Int]

-- | The following equations hold for <a>fullPathUp</a> and
--   <a>fullPathDown</a>:
--   
--   <pre>
--   fullPathUp == reverse . fullPathDown
--   loc == foldr unsafeMoveDown (moveTop loc) (fullPathUp loc)
--   </pre>
fullPathUp :: Foldable f => Loc f -> [Int]

-- | Moves to the top, by repeatedly moving up.
moveTop :: Traversable f => Loc f -> Loc f

-- | Moves left until it can. It should be faster than repeated left steps.
leftmost :: Traversable f => Loc f -> Loc f

-- | Moves right until it can. It should be faster than repeated right
--   steps.
rightmost :: Traversable f => Loc f -> Loc f
unsafeMoveDown :: Traversable f => Int -> Loc f -> Loc f
unsafeMoveDownL :: Traversable f => Loc f -> Loc f
unsafeMoveDownR :: Traversable f => Loc f -> Loc f
unsafeMoveUp :: Traversable f => Loc f -> Loc f
unsafeMoveLeft, unsafeMoveRight :: Traversable f => Loc f -> Loc f
instance ReadF f => Read (Loc f)
instance ReadF f => Read (Path f)
instance ShowF f => Show (Loc f)
instance ShowF f => Show (Path f)
instance EqF f => Eq (Loc f)
instance EqF f => Eq (Path f)


-- | Changing the structure of a tree.
module Data.Generics.Fixplate.Structure

-- | The type of natural transformations.
type NatTrafo f g = forall a. f a -> g a

-- | Changing the structure of a tree.
restructure :: Functor f => NatTrafo f g -> Mu f -> Mu g

-- | Lifting natural transformations to annotations.
liftAnn :: (f e -> g e) -> Ann f a e -> Ann g a e


-- | This library provides Uniplate-style generic traversals for
--   fixed-point types. The advantages of using fixed-point types instead
--   of explicit recursion are the following:
--   
--   <ul>
--   <li>we can add attributes to the nodes of an existing tree;</li>
--   <li>there is no need for a custom type class, we can build everything
--   on the top of <tt>Functor</tt>, <tt>Foldable</tt> and
--   <tt>Traversable</tt>, for which GHC can derive the instances for
--   us;</li>
--   <li>some operations can retain the structure of the tree, instead
--   flattening it into a list;</li>
--   <li>it is quite straightforward to provide a generic zipper.</li>
--   </ul>
--   
--   The main disadvantage is that it does not work well for mutually
--   recursive data types, and that pattern matching becomes more tedious
--   (but there are partial solutions for the latter).
--   
--   Consider as an example the following simple expression language,
--   encoded by a recursive algebraic data type:
--   
--   <pre>
--   Expr 
--     = Kst Int 
--     | Var String 
--     | Add Expr Expr
--     deriving (Eq,Show)
--   </pre>
--   
--   We can open up the recursion, and obtain a <i>functor</i> instead:
--   
--   <pre>
--   Expr1 e 
--     = Kst Int 
--     | Var String 
--     | Add e e 
--     deriving (Eq,Show,Functor,Foldable,Traversable)
--   </pre>
--   
--   The fixed-point type <a>Mu</a><tt> Expr1</tt> is isomorphic to
--   <tt>Expr</tt>. However, we can also add some attributes to the nodes:
--   The type <a>Attr</a> <tt>Expr1 a = </tt><a>Mu</a><tt>
--   (</tt><a>Ann</a><tt> Expr1 a)</tt> is the type of with the same
--   structure, but with each node having an extra field of type
--   <tt>a</tt>.
--   
--   The functions in this library work on types like that: <a>Mu</a><tt>
--   f</tt>, where <tt>f</tt> is a functor, and sometimes explicitely on
--   <a>Attr</a><tt> f a</tt>.
--   
--   This module re-exports most of the functionality present in the
--   library.
--   
--   The library should be fully Haskell98 compatible, with the exception
--   of the module <a>Data.Generics.Fixplate.Structure</a>, which needs the
--   <tt>Rank2Types</tt> extension. For compatibility, the functionality of
--   this module is at the moment only provided when compiled with GHC or
--   Hugs.
module Data.Generics.Fixplate

-- | The <a>Functor</a> class is used for types that can be mapped over.
--   Instances of <a>Functor</a> should satisfy the following laws:
--   
--   <pre>
--   fmap id  ==  id
--   fmap (f . g)  ==  fmap f . fmap g
--   </pre>
--   
--   The instances of <a>Functor</a> for lists, <a>Maybe</a> and <a>IO</a>
--   satisfy these laws.
class Functor (f :: * -> *)
fmap :: Functor f => (a -> b) -> f a -> f b

-- | Data structures that can be folded.
--   
--   Minimal complete definition: <a>foldMap</a> or <a>foldr</a>.
--   
--   For example, given a data type
--   
--   <pre>
--   data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--   </pre>
--   
--   a suitable instance would be
--   
--   <pre>
--   instance Foldable Tree where
--      foldMap f Empty = mempty
--      foldMap f (Leaf x) = f x
--      foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--   </pre>
--   
--   This is suitable even for abstract types, as the monoid is assumed to
--   satisfy the monoid laws. Alternatively, one could define
--   <tt>foldr</tt>:
--   
--   <pre>
--   instance Foldable Tree where
--      foldr f z Empty = z
--      foldr f z (Leaf x) = f x z
--      foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--   </pre>
class Foldable (t :: * -> *)
fold :: (Foldable t, Monoid m) => t m -> m
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b
foldl :: Foldable t => (a -> b -> a) -> a -> t b -> a
foldr1 :: Foldable t => (a -> a -> a) -> t a -> a
foldl1 :: Foldable t => (a -> a -> a) -> t a -> a

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