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


-- | Uniplate-style generic traversals for optionally annotated fixed-point types.
--   
--   Uniplate-style generic traversals for fixed-point types, which can be
--   optionally annotated with attributes. We also provide recursion
--   schemes, a generic zipper, generic pretty-printer, generic tries,
--   generic hashing, and generic tree visualization. See the module
--   <a>Data.Generics.Fixplate</a> and then the individual modules for more
--   detailed information.
@package fixplate
@version 0.1.7


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

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

-- | We call a tree "atomic" if it has no subtrees.
isAtom :: Foldable f => Mu f -> Bool

-- | Type of annotations
data Ann f a b
Ann :: a -> f b -> Ann f a b

-- | the annotation
[attr] :: Ann f a b -> a

-- | the original functor
[unAnn] :: Ann f a b -> f b

-- | Annotated fixed-point type. Equivalent to <tt>CoFree f a</tt>
type Attr f a = Mu (Ann f a)

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

-- | Categorical dual of <a>Ann</a>.
data CoAnn f a b
Pure :: a -> CoAnn f a b
CoAnn :: (f b) -> CoAnn f a b

-- | Categorical dual of <a>Attr</a>. Equivalent to <tt>Free f a</tt>
type CoAttr f a = Mu (CoAnn f a)

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

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

-- | This a data type defined to be a place-holder for childs. It is used
--   in tree drawing, hashing, and <tt>Shape</tt>.
--   
--   It is deliberately not made an instance of <a>Show</a>, so that you
--   can choose your preferred style. For example, an acceptable choice is
--   
--   <pre>
--   instance Show Hole where show _ = "_"
--   </pre>
data Hole
Hole :: Hole

-- | "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)
showF :: (ShowF f, Show a) => f a -> String
showsF :: (ShowF f, Show a) => f a -> ShowS

-- | NOTE: The <a>EqF</a> instance for annotations compares both the
--   annotations and the original part.

-- | NOTE: The <a>OrdF</a> instance for annotations first compares the
--   <i>annotations</i>, and then the functor part. If this is not the
--   desired behaviour (it's not clear to me at the moment what is the good
--   default here), you can use the standard newtype trick to define a new
--   behaviour.

-- | 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 (and
--   Comonad). This is necessary since Haskell does not allow partial
--   application of type synonyms.
--   
--   Equivalent to the co-free comonad.
newtype Attrib f a
Attrib :: Attr f a -> Attrib f a
[unAttrib] :: Attrib f a -> Attr f a

-- | Categorial dual of <a>Attrib</a>. Equivalent to the free monad.
newtype CoAttrib f a
CoAttrib :: CoAttr f a -> CoAttrib f a
[unCoAttrib] :: CoAttrib f a -> CoAttr f a
instance GHC.Classes.Ord Data.Generics.Fixplate.Base.Hole
instance GHC.Classes.Eq Data.Generics.Fixplate.Base.Hole
instance (GHC.Show.Show a, GHC.Show.Show (f b)) => GHC.Show.Show (Data.Generics.Fixplate.Base.CoAnn f a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (f b)) => GHC.Classes.Ord (Data.Generics.Fixplate.Base.CoAnn f a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (f b)) => GHC.Classes.Eq (Data.Generics.Fixplate.Base.CoAnn f a b)
instance (GHC.Show.Show a, GHC.Show.Show (f b)) => GHC.Show.Show (Data.Generics.Fixplate.Base.Ann f a b)
instance (GHC.Classes.Ord a, GHC.Classes.Ord (f b)) => GHC.Classes.Ord (Data.Generics.Fixplate.Base.Ann f a b)
instance (GHC.Classes.Eq a, GHC.Classes.Eq (f b)) => GHC.Classes.Eq (Data.Generics.Fixplate.Base.Ann f a b)
instance Data.Generics.Fixplate.Base.EqF f => GHC.Classes.Eq (Data.Generics.Fixplate.Base.Mu f)
instance Data.Generics.Fixplate.Base.OrdF f => GHC.Classes.Ord (Data.Generics.Fixplate.Base.Mu f)
instance Data.Generics.Fixplate.Base.ShowF f => GHC.Show.Show (Data.Generics.Fixplate.Base.Mu f)
instance Data.Generics.Fixplate.Base.ReadF f => GHC.Read.Read (Data.Generics.Fixplate.Base.Mu f)
instance (GHC.Classes.Eq a, Data.Generics.Fixplate.Base.EqF f) => Data.Generics.Fixplate.Base.EqF (Data.Generics.Fixplate.Base.Ann f a)
instance (GHC.Classes.Ord a, Data.Generics.Fixplate.Base.OrdF f) => Data.Generics.Fixplate.Base.OrdF (Data.Generics.Fixplate.Base.Ann f a)
instance (GHC.Show.Show a, Data.Generics.Fixplate.Base.ShowF f) => Data.Generics.Fixplate.Base.ShowF (Data.Generics.Fixplate.Base.Ann f a)
instance (GHC.Read.Read a, Data.Generics.Fixplate.Base.ReadF f) => Data.Generics.Fixplate.Base.ReadF (Data.Generics.Fixplate.Base.Ann f a)
instance (GHC.Classes.Eq a, Data.Generics.Fixplate.Base.EqF f) => Data.Generics.Fixplate.Base.EqF (Data.Generics.Fixplate.Base.CoAnn f a)
instance (GHC.Classes.Ord a, Data.Generics.Fixplate.Base.OrdF f) => Data.Generics.Fixplate.Base.OrdF (Data.Generics.Fixplate.Base.CoAnn f a)
instance (GHC.Show.Show a, Data.Generics.Fixplate.Base.ShowF f) => Data.Generics.Fixplate.Base.ShowF (Data.Generics.Fixplate.Base.CoAnn f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Generics.Fixplate.Base.Ann f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Generics.Fixplate.Base.Ann f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Generics.Fixplate.Base.Ann f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Generics.Fixplate.Base.CoAnn f a)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Generics.Fixplate.Base.CoAnn f a)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Generics.Fixplate.Base.CoAnn f a)
instance (Data.Generics.Fixplate.Base.ShowF f, GHC.Show.Show a) => GHC.Show.Show (Data.Generics.Fixplate.Base.Attrib f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Generics.Fixplate.Base.Attrib f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Generics.Fixplate.Base.Attrib f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Generics.Fixplate.Base.Attrib f)
instance (Data.Generics.Fixplate.Base.ShowF f, GHC.Show.Show a) => GHC.Show.Show (Data.Generics.Fixplate.Base.CoAttrib f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Generics.Fixplate.Base.CoAttrib f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Generics.Fixplate.Base.CoAttrib f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Generics.Fixplate.Base.CoAttrib f)
instance GHC.Base.Functor f => GHC.Base.Applicative (Data.Generics.Fixplate.Base.CoAttrib f)
instance GHC.Base.Functor f => GHC.Base.Monad (Data.Generics.Fixplate.Base.CoAttrib f)


-- | Recursion schemes, also known as scary named folds...
module Data.Generics.Fixplate.Morphisms

-- | A <i>catamorphism</i> is the generalization of right fold from lists
--   to trees.
cata :: Functor f => (f a -> a) -> Mu f -> a

-- | A <i>paramorphism</i> is a more general version of the catamorphism.
para :: Functor f => (f (Mu f, a) -> a) -> Mu f -> a

-- | Another version of <a>para</a> (a bit less natural in some sense).
para' :: Functor f => (Mu f -> f a -> a) -> Mu f -> a

-- | A list version of <a>para</a> (compare with Uniplate)
paraList :: (Functor f, Foldable f) => (Mu f -> [a] -> a) -> Mu f -> a

-- | An <i>anamorphism</i> is simply an unfold. Probably not very useful in
--   this context.
ana :: Functor f => (a -> f a) -> a -> Mu f

-- | An <i>apomorphism</i> is a generalization of the anamorphism.
apo :: Functor f => (a -> f (Either (Mu 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)

-- | A <i>zygomorphism</i> is a basically a catamorphism inside another
--   catamorphism. It could be implemented (somewhat wastefully) by first
--   annotating each subtree with the corresponding values of the inner
--   catamorphism (<tt>synthCata</tt>), then running a paramorphims on the
--   annotated tree:
--   
--   <pre>
--   zygo_ g h == para u . synthCata g 
--     where
--       u = h . fmap (first attribute) . unAnn
--       first f (x,y) = (f x, y)
--   </pre>
zygo_ :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Mu f -> a
zygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Mu f -> (b, a)

-- | Histomorphism. This is a kind of glorified cata/paramorphism, after
--   all:
--   
--   <pre>
--   cata f == histo (f . fmap attribute)
--   para f == histo (f . fmap (\t -&gt; (forget t, attribute t)))
--   </pre>
histo :: Functor f => (f (Attr f a) -> a) -> Mu f -> a

-- | Futumorphism. This is a more interesting unfold.
futu :: Functor f => (a -> f (CoAttr f a)) -> a -> Mu f

-- | Monadic catamorphism.
cataM :: (Monad m, Traversable f) => (f a -> m a) -> Mu f -> m a
cataM_ :: (Monad m, Traversable f) => (f a -> m a) -> Mu f -> m ()

-- | Monadic paramorphism.
paraM :: (Monad m, Traversable f) => (f (Mu f, a) -> m a) -> Mu f -> m a
paraM_ :: (Monad m, Traversable f) => (f (Mu f, a) -> m a) -> Mu f -> m ()

-- | Another version of <a>paraM</a>.
paraM' :: (Monad m, Traversable f) => (Mu f -> f a -> m a) -> Mu f -> m a


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

-- | List of elements of a structure, from left to right.
toList :: Foldable t => forall a. t a -> [a]

-- | Equivalent to <tt>reverse . toList</tt>.
toRevList :: Foldable f => f a -> [a]

-- | The <a>mapAccumL</a> function behaves like a combination of
--   <a>fmap</a> and <tt>foldl</tt>; 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

-- | This a data type defined to be a place-holder for childs. It is used
--   in tree drawing, hashing, and <tt>Shape</tt>.
--   
--   It is deliberately not made an instance of <a>Show</a>, so that you
--   can choose your preferred style. For example, an acceptable choice is
--   
--   <pre>
--   instance Show Hole where show _ = "_"
--   </pre>
data Hole
Hole :: Hole

-- | 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 Hole }
--   </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 Data.Generics.Fixplate.Base.EqF f => GHC.Classes.Eq (Data.Generics.Fixplate.Open.Shape f)
instance Data.Generics.Fixplate.Base.OrdF f => GHC.Classes.Ord (Data.Generics.Fixplate.Open.Shape f)
instance GHC.Show.Show Data.Generics.Fixplate.Open.Void
instance (GHC.Base.Functor f, Data.Generics.Fixplate.Base.ShowF f) => GHC.Show.Show (Data.Generics.Fixplate.Open.Shape f)


-- | Uniplate-style traversals.
--   
--   Toy example: Consider our favourite data type
--   
--   <pre>
--   data Expr e 
--     = Kst Int 
--     | Var String 
--     | Add e e 
--     deriving (Eq,Show,Functor,Foldable,Traversable)
--   
--   instance ShowF Expr where showsPrecF = showsPrec
--   </pre>
--   
--   and write a function simplifying additions with zero:
--   
--   <pre>
--   simplifyAdd :: Mu Expr -&gt; Mu Expr
--   simplifyAdd = transform worker where
--     worker expr = case expr of
--       Fix (Add x (Fix (Kst 0))) -&gt; x    -- 0+x = x
--       Fix (Add (Fix (Kst 0)) y) -&gt; y    -- x+0 = 0
--       _ -&gt; expr
--   </pre>
--   
--   Unfortunately, all these <a>Fix</a> wrappers are rather ugly; but they
--   are straightforward to put in, and in principle one could use Template
--   Haskell quasi-quotation to generate patterns.
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. This is basically just
--   <a>fmap</a>.
descend :: Functor f => (Mu f -> Mu f) -> Mu f -> Mu f

-- | Similarly, this is basically just <a>mapM</a>.
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)

-- | Bottom-up transformation (typically "shallow", that is, restricted to
--   a single level) which can change the structure functor (actually
--   <a>transform</a> is a special case of this).
restructure :: Functor f => (f (Mu g) -> g (Mu g)) -> Mu f -> Mu g
restructureM :: (Traversable f, Monad m) => (f (Mu g) -> m (g (Mu g))) -> Mu f -> m (Mu g)

-- | 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, and
--   partly by recursion schemes.
--   
--   TODO: better organization / interface to all these functions...
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 (and
--   Comonad). This is necessary since Haskell does not allow partial
--   application of type synonyms.
--   
--   Equivalent to the co-free comonad.
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>)
--   
--   See also <a>synthCata</a>.
synthetise :: Functor f => (f a -> a) -> Mu f -> Attr f a

-- | Generalization of <tt>scanr</tt> for trees. See also <a>scanCata</a>.
synthetise' :: Functor f => (a -> f b -> b) -> Attr f a -> Attr f b

-- | List version of <a>synthetise</a> (compare with Uniplate)
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)

-- | Synonym for <a>synthetise</a>, motivated by the equation
--   
--   <pre>
--   attribute . synthCata f == cata f
--   </pre>
--   
--   That is, it attributes all subtrees with the result of the
--   corresponding catamorphism.
synthCata :: Functor f => (f a -> a) -> Mu f -> Attr f a

-- | Synonym for <a>synthetise'</a>. Note that this could be a special case
--   of <a>synthCata</a>:
--   
--   <pre>
--   scanCata f == annZipWith (flip const) . synthCata (\(Ann a x) -&gt; f a x)
--   </pre>
--   
--   Catamorphim (<tt>cata</tt>) is the generalization of <tt>foldr</tt>
--   from lists to trees; <a>synthCata</a> is one generalization of
--   <tt>scanr</tt>, and <a>scanCata</a> is another generalization.
scanCata :: Functor f => (a -> f b -> b) -> Attr f a -> Attr f b

-- | Attributes all subtrees with the result of the corresponding
--   paramorphism.
--   
--   <pre>
--   attribute . synthPara f == para f
--   </pre>
synthPara :: Functor f => (f (Mu f, a) -> a) -> Mu f -> Attr f a

-- | Another version of <a>synthPara</a>.
--   
--   <pre>
--   attribute . synthPara' f == para' f
--   </pre>
synthPara' :: Functor f => (Mu f -> f a -> a) -> Mu f -> Attr f a
scanPara :: Functor f => (Attr f a -> f b -> b) -> Attr f a -> Attr f b

-- | Synthetising zygomorphism.
--   
--   <pre>
--   attribute . synthZygo_ g h == zygo_ g h
--   </pre>
synthZygo_ :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Mu f -> Attr f a
synthZygo :: Functor f => (f b -> b) -> (f (b, a) -> a) -> Mu f -> Attr f (b, a)
synthZygoWith :: Functor f => (b -> a -> c) -> (f b -> b) -> (f (b, a) -> a) -> Mu f -> Attr f c

-- | Accumulating catamorphisms. Generalization of <a>mapAccumR</a> from
--   lists to trees.
synthAccumCata :: Functor f => (f acc -> (acc, b)) -> Mu f -> (acc, Attr f b)

-- | Accumulating paramorphisms.
synthAccumPara' :: Functor f => (Mu f -> f acc -> (acc, b)) -> Mu f -> (acc, Attr f b)

-- | Could be a special case of <a>synthAccumCata</a>:
--   
--   <pre>
--   mapAccumCata f == second (annZipWith (flip const)) . synthAccumCata (\(Ann b t) -&gt; f b t) 
--     where second g (x,y) = (x, g y)
--   </pre>
mapAccumCata :: Functor f => (f acc -> b -> (acc, c)) -> Attr f b -> (acc, Attr f c)

-- | Synonym for <a>synthetiseM</a>. If you don't need the result, use
--   <tt>cataM_</tt> instead.
synthCataM :: (Traversable f, Monad m) => (f a -> m a) -> Mu f -> m (Attr f a)

-- | Monadic version of <a>synthPara</a>. If you don't need the result, use
--   <tt>paraM_</tt> instead.
synthParaM :: (Traversable f, Monad m) => (f (Mu f, a) -> m a) -> Mu f -> m (Attr f a)

-- | Monadic version of <a>synthPara'</a>.
synthParaM' :: (Traversable f, Monad m) => (Mu f -> 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> from lists to trees.
inherit' :: Functor f => (a -> b -> a) -> a -> Attr f b -> Attr f a

-- | Generalization of <a>inherit</a>. TODO: better name?
inherit2 :: Functor f => (Mu f -> a -> (b, a)) -> a -> Mu f -> Attr f b

-- | 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
synthTransform' :: Traversable f => (f (Attr 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
synthRewrite' :: Traversable f => (f (Attr 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


-- | Generic ascii art / graphviz drawing of trees.
--   
--   Suggestions for drawing styles are welcome.
--   
--   TODO:
--   
--   <ul>
--   <li>make the style customizable</li>
--   <li>the same for graphviz</li>
--   </ul>
module Data.Generics.Fixplate.Draw

-- | Prints a tree. It is defined simply as
--   
--   <pre>
--   drawTree = putStrLn . showTree
--   </pre>
drawTree :: (Functor f, Foldable f, ShowF f) => Mu f -> IO ()

-- | Creates a string representation which can be printed with
--   <a>putStrLn</a>.
showTree :: (Functor f, Foldable f, ShowF f) => Mu f -> String

-- | Generate a graphviz <tt>.dot</tt> file
graphvizTree :: (Traversable f, ShowF f) => Mu f -> String
drawTreeWith :: (Functor f, Foldable f) => (f Hole -> String) -> Mu f -> IO ()
showTreeWith :: (Functor f, Foldable f) => (f Hole -> String) -> Mu f -> String
graphvizTreeWith :: (Traversable f) => (f Hole -> String) -> Mu f -> String
instance GHC.Show.Show Data.Generics.Fixplate.Draw.Void


-- | 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 :: Traversable f => Loc f -> Loc f
unsafeMoveRight :: Traversable f => Loc f -> Loc f
instance Data.Generics.Fixplate.Base.EqF f => GHC.Classes.Eq (Data.Generics.Fixplate.Zipper.Path f)
instance Data.Generics.Fixplate.Base.EqF f => GHC.Classes.Eq (Data.Generics.Fixplate.Zipper.Loc f)
instance Data.Generics.Fixplate.Base.ShowF f => GHC.Show.Show (Data.Generics.Fixplate.Zipper.Path f)
instance Data.Generics.Fixplate.Base.ShowF f => GHC.Show.Show (Data.Generics.Fixplate.Zipper.Loc f)
instance Data.Generics.Fixplate.Base.ReadF f => GHC.Read.Read (Data.Generics.Fixplate.Zipper.Path f)
instance Data.Generics.Fixplate.Base.ReadF f => GHC.Read.Read (Data.Generics.Fixplate.Zipper.Loc f)


-- | Generalized tries. "Normal" tries encode finite maps from lists to
--   arbitrary values, where the common prefixes are shared. Here we do the
--   same for trees, generically.
--   
--   See also
--   
--   <ul>
--   <li>Connelly, Morris: A generalization of the trie data structure</li>
--   <li>Ralf Hinze: Generalizing Generalized Tries</li>
--   </ul>
--   
--   This module should be imported qualified.
module Data.Generics.Fixplate.Trie

-- | <a>Trie</a> is an efficient(?) implementation of finite maps from
--   <tt>(Mu f)</tt> to an arbitrary type <tt>v</tt>.
data Trie f v
empty :: (Functor f, Foldable f, OrdF f) => Trie f a
singleton :: (Functor f, Foldable f, OrdF f) => Mu f -> a -> Trie f a

-- | TODO: more efficient implementation?
fromList :: (Traversable f, OrdF f) => [(Mu f, a)] -> Trie f a
toList :: (Traversable f, OrdF f) => Trie f a -> [(Mu f, a)]

-- | Creates a trie-multiset from a list of trees.
bag :: (Functor f, Foldable f, OrdF f) => [Mu f] -> Trie f Int

-- | This is equivalent to
--   
--   <pre>
--   universeBag == bag . universe
--   </pre>
--   
--   TODO: more efficient implementation? and better name
universeBag :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f Int

-- | We attribute each node with the multiset of all its subtrees. TODO:
--   better name
christmasTree :: (Functor f, Foldable f, OrdF f) => Mu f -> Attr f (Trie f Int)
lookup :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f a -> Maybe a
insert :: (Functor f, Foldable f, OrdF f) => Mu f -> a -> Trie f a -> Trie f a
insertWith :: (Functor f, Foldable f, OrdF f) => (a -> b) -> (a -> b -> b) -> Mu f -> a -> Trie f b -> Trie f b
delete :: (Functor f, Foldable f, OrdF f) => Mu f -> Trie f a -> Trie f a
update :: (Functor f, Foldable f, OrdF f) => (a -> Maybe a) -> Mu f -> Trie f a -> Trie f a
intersection :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f b -> Trie f a
intersectionWith :: (Functor f, Foldable f, OrdF f) => (a -> b -> c) -> Trie f a -> Trie f b -> Trie f c

-- | Union is left-biased:
--   
--   <pre>
--   union == unionWith const
--   </pre>
union :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f a -> Trie f a
unionWith :: (Functor f, Foldable f, OrdF f) => (a -> a -> a) -> Trie f a -> Trie f a -> Trie f a
difference :: (Functor f, Foldable f, OrdF f) => Trie f a -> Trie f b -> Trie f a
differenceWith :: (Functor f, Foldable f, OrdF f) => (a -> b -> Maybe a) -> Trie f a -> Trie f b -> Trie f a
instance Data.Generics.Fixplate.Base.EqF f => GHC.Classes.Eq (Data.Generics.Fixplate.Trie.HoleF f)
instance Data.Generics.Fixplate.Base.OrdF f => GHC.Classes.Ord (Data.Generics.Fixplate.Trie.HoleF f)


-- | This library provides Uniplate-style generic traversals and other
--   recursion schemes for fixed-point types. There are many advantages of
--   using fixed-point types instead of explicit recursion:
--   
--   <ul>
--   <li>we can easily 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 <a>Functor</a>, <a>Foldable</a> and <a>Traversable</a>,
--   for which GHC can derive the instances for us;</li>
--   <li>we can provide interesting recursion schemes</li>
--   <li>some operations can retain the structure of the tree, instead
--   flattening it into a list;</li>
--   <li>it is relatively straightforward to provide generic
--   implementations of the zipper, tries, tree drawing, hashing,
--   etc...</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>
--   data 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>
--   data 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>.
--   
--   The organization of the modules (excluding Util.*) is the following:
--   
--   <ul>
--   <li><a>Data.Generics.Fixplate.Base</a> - core types and type
--   classes</li>
--   <li><a>Data.Generics.Fixplate.Functor</a> - sum and product
--   functors</li>
--   <li><a>Data.Generics.Fixplate.Traversals</a> - Uniplate-style
--   traversals</li>
--   <li><a>Data.Generics.Fixplate.Morphisms</a> - recursion schemes</li>
--   <li><a>Data.Generics.Fixplate.Attributes</a> - annotated trees</li>
--   <li><a>Data.Generics.Fixplate.Open</a> - functions operating on
--   functors</li>
--   <li><a>Data.Generics.Fixplate.Zipper</a> - generic zipper</li>
--   <li><a>Data.Generics.Fixplate.Draw</a> - generic tree drawing (both
--   ASCII and graphviz)</li>
--   <li><a>Data.Generics.Fixplate.Pretty</a> - pretty-printing of
--   expression trees</li>
--   <li><a>Data.Generics.Fixplate.Trie</a> - generic generalized
--   tries</li>
--   <li><a>Data.Generics.Fixplate.Hash</a> - annotating trees with their
--   hashes</li>
--   </ul>
--   
--   This module re-exports the most common functionality present in the
--   library (but not for example the zipper, tries, hashing).
--   
--   The library itself should be fully Haskell98 compatible; no language
--   extensions are used. The only exception is the
--   <a>Data.Generics.Fixplate.Functor</a> module, which uses the
--   TypeOperators language extension for syntactic convenience (but this
--   is not used anywhere else).
--   
--   Note: to obtain <a>Eq</a>, <a>Ord</a>, <a>Show</a>, <a>Read</a> and
--   other instances for fixed point types like <tt>Mu Expr1</tt>, consult
--   the documentation of the <a>EqF</a> type class (cf. the related
--   <a>OrdF</a>, <a>ShowF</a> and <a>ReadF</a> classes)
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 :: (a -> b) -> f a -> f b

-- | Replace all locations in the input with the same value. The default
--   definition is <tt><a>fmap</a> . <a>const</a></tt>, but this may be
--   overridden with a more efficient version.
(<$) :: a -> f b -> f a

-- | Data structures that can be folded.
--   
--   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>
--   
--   <tt>Foldable</tt> instances are expected to satisfy the following
--   laws:
--   
--   <pre>
--   foldr f z t = appEndo (foldMap (Endo . f) t ) z
--   </pre>
--   
--   <pre>
--   foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--   </pre>
--   
--   <pre>
--   fold = foldMap id
--   </pre>
--   
--   <tt>sum</tt>, <tt>product</tt>, <tt>maximum</tt>, and <tt>minimum</tt>
--   should all be essentially equivalent to <tt>foldMap</tt> forms, such
--   as
--   
--   <pre>
--   sum = getSum . foldMap Sum
--   </pre>
--   
--   but may be less defined.
--   
--   If the type is also a <a>Functor</a> instance, it should satisfy
--   
--   <pre>
--   foldMap f = fold . fmap f
--   </pre>
--   
--   which implies that
--   
--   <pre>
--   foldMap f . fmap g = foldMap (f . g)
--   </pre>
class Foldable (t :: * -> *)

-- | Map each element of the structure to a monoid, and combine the
--   results.
foldMap :: Monoid m => (a -> m) -> t a -> m

-- | Right-associative fold of a structure.
--   
--   In the case of lists, <a>foldr</a>, when applied to a binary operator,
--   a starting value (typically the right-identity of the operator), and a
--   list, reduces the list using the binary operator, from right to left:
--   
--   <pre>
--   foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
--   </pre>
--   
--   Note that, since the head of the resulting expression is produced by
--   an application of the operator to the first element of the list,
--   <a>foldr</a> can produce a terminating expression from an infinite
--   list.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldr f z = <a>foldr</a> f z . <a>toList</a>
--   </pre>
foldr :: (a -> b -> b) -> b -> t a -> b

-- | Left-associative fold of a structure.
--   
--   In the case of lists, <a>foldl</a>, when applied to a binary operator,
--   a starting value (typically the left-identity of the operator), and a
--   list, reduces the list using the binary operator, from left to right:
--   
--   <pre>
--   foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--   </pre>
--   
--   Note that to produce the outermost application of the operator the
--   entire input list must be traversed. This means that <a>foldl'</a>
--   will diverge if given an infinite list.
--   
--   Also note that if you want an efficient left-fold, you probably want
--   to use <a>foldl'</a> instead of <a>foldl</a>. The reason for this is
--   that latter does not force the "inner" results (e.g. <tt>z <tt>f</tt>
--   x1</tt> in the above example) before applying them to the operator
--   (e.g. to <tt>(<tt>f</tt> x2)</tt>). This results in a thunk chain
--   <tt>O(n)</tt> elements long, which then must be evaluated from the
--   outside-in.
--   
--   For a general <a>Foldable</a> structure this should be semantically
--   identical to,
--   
--   <pre>
--   foldl f z = <a>foldl</a> f z . <a>toList</a>
--   </pre>
foldl :: (b -> a -> b) -> b -> t a -> b

-- | A variant of <a>foldr</a> that has no base case, and thus may only be
--   applied to non-empty structures.
--   
--   <pre>
--   <a>foldr1</a> f = <a>foldr1</a> f . <a>toList</a>
--   </pre>
foldr1 :: (a -> a -> a) -> t a -> a

-- | A variant of <a>foldl</a> that has no base case, and thus may only be
--   applied to non-empty structures.
--   
--   <pre>
--   <a>foldl1</a> f = <a>foldl1</a> f . <a>toList</a>
--   </pre>
foldl1 :: (a -> a -> a) -> t a -> a

-- | Test whether the structure is empty. The default implementation is
--   optimized for structures that are similar to cons-lists, because there
--   is no general way to do better.
null :: t a -> Bool

-- | Returns the size/length of a finite structure as an <a>Int</a>. The
--   default implementation is optimized for structures that are similar to
--   cons-lists, because there is no general way to do better.
length :: t a -> Int

-- | Does the element occur in the structure?
elem :: Eq a => a -> t a -> Bool

-- | The largest element of a non-empty structure.
maximum :: Ord a => t a -> a

-- | The least element of a non-empty structure.
minimum :: Ord a => t a -> a

-- | The <a>sum</a> function computes the sum of the numbers of a
--   structure.
sum :: Num a => t a -> a

-- | The <a>product</a> function computes the product of the numbers of a
--   structure.
product :: Num a => t a -> a

-- | Functors representing data structures that can be traversed from left
--   to right.
--   
--   A definition of <a>traverse</a> must satisfy the following laws:
--   
--   <ul>
--   <li><i><i>naturality</i></i> <tt>t . <a>traverse</a> f =
--   <a>traverse</a> (t . f)</tt> for every applicative transformation
--   <tt>t</tt></li>
--   <li><i><i>identity</i></i> <tt><a>traverse</a> Identity =
--   Identity</tt></li>
--   <li><i><i>composition</i></i> <tt><a>traverse</a> (Compose .
--   <a>fmap</a> g . f) = Compose . <a>fmap</a> (<a>traverse</a> g) .
--   <a>traverse</a> f</tt></li>
--   </ul>
--   
--   A definition of <a>sequenceA</a> must satisfy the following laws:
--   
--   <ul>
--   <li><i><i>naturality</i></i> <tt>t . <a>sequenceA</a> =
--   <a>sequenceA</a> . <a>fmap</a> t</tt> for every applicative
--   transformation <tt>t</tt></li>
--   <li><i><i>identity</i></i> <tt><a>sequenceA</a> . <a>fmap</a> Identity
--   = Identity</tt></li>
--   <li><i><i>composition</i></i> <tt><a>sequenceA</a> . <a>fmap</a>
--   Compose = Compose . <a>fmap</a> <a>sequenceA</a> .
--   <a>sequenceA</a></tt></li>
--   </ul>
--   
--   where an <i>applicative transformation</i> is a function
--   
--   <pre>
--   t :: (Applicative f, Applicative g) =&gt; f a -&gt; g a
--   </pre>
--   
--   preserving the <a>Applicative</a> operations, i.e.
--   
--   <ul>
--   <li><pre>t (<a>pure</a> x) = <a>pure</a> x</pre></li>
--   <li><pre>t (x <a>&lt;*&gt;</a> y) = t x <a>&lt;*&gt;</a> t
--   y</pre></li>
--   </ul>
--   
--   and the identity functor <tt>Identity</tt> and composition of functors
--   <tt>Compose</tt> are defined as
--   
--   <pre>
--   newtype Identity a = Identity a
--   
--   instance Functor Identity where
--     fmap f (Identity x) = Identity (f x)
--   
--   instance Applicative Identity where
--     pure x = Identity x
--     Identity f &lt;*&gt; Identity x = Identity (f x)
--   
--   newtype Compose f g a = Compose (f (g a))
--   
--   instance (Functor f, Functor g) =&gt; Functor (Compose f g) where
--     fmap f (Compose x) = Compose (fmap (fmap f) x)
--   
--   instance (Applicative f, Applicative g) =&gt; Applicative (Compose f g) where
--     pure x = Compose (pure (pure x))
--     Compose f &lt;*&gt; Compose x = Compose ((&lt;*&gt;) &lt;$&gt; f &lt;*&gt; x)
--   </pre>
--   
--   (The naturality law is implied by parametricity.)
--   
--   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 :: * -> *)

-- | Map each element of a structure to an action, evaluate these actions
--   from left to right, and collect the results. For a version that
--   ignores the results see <a>traverse_</a>.
traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

-- | Evaluate each action in the structure from left to right, and and
--   collect the results. For a version that ignores the results see
--   <a>sequenceA_</a>.
sequenceA :: Applicative f => t (f a) -> f (t a)

-- | Map each element of a structure to a monadic action, evaluate these
--   actions from left to right, and collect the results. For a version
--   that ignores the results see <a>mapM_</a>.
mapM :: Monad m => (a -> m b) -> t a -> m (t b)

-- | Evaluate each monadic action in the structure from left to right, and
--   collect the results. For a version that ignores the results see
--   <a>sequence_</a>.
sequence :: Monad m => t (m a) -> m (t a)


-- | Sum and product functors, with the usual instances. You can in
--   principle use these to extend existing expressions, for example
--   
--   <pre>
--   type ExtendedExpression = Mu (Expr :+: Custom)
--   </pre>
--   
--   This module uses the TypeOperators language extension for convenience.
module Data.Generics.Fixplate.Functor

-- | Sum of two functors
data (:+:) f g a
InL :: (f a) -> (:+:) f g a
InR :: (g a) -> (:+:) f g a

-- | Product of two functors
data (:*:) f g a
(:*:) :: (f a) -> (g a) -> (:*:) f g a
instance (GHC.Show.Show (f a), GHC.Show.Show (g a)) => GHC.Show.Show ((Data.Generics.Fixplate.Functor.:*:) f g a)
instance (GHC.Classes.Ord (f a), GHC.Classes.Ord (g a)) => GHC.Classes.Ord ((Data.Generics.Fixplate.Functor.:*:) f g a)
instance (GHC.Classes.Eq (f a), GHC.Classes.Eq (g a)) => GHC.Classes.Eq ((Data.Generics.Fixplate.Functor.:*:) f g a)
instance (GHC.Show.Show (f a), GHC.Show.Show (g a)) => GHC.Show.Show ((Data.Generics.Fixplate.Functor.:+:) f g a)
instance (GHC.Classes.Ord (f a), GHC.Classes.Ord (g a)) => GHC.Classes.Ord ((Data.Generics.Fixplate.Functor.:+:) f g a)
instance (GHC.Classes.Eq (f a), GHC.Classes.Eq (g a)) => GHC.Classes.Eq ((Data.Generics.Fixplate.Functor.:+:) f g a)
instance (GHC.Base.Functor f, GHC.Base.Functor g) => GHC.Base.Functor (f Data.Generics.Fixplate.Functor.:+: g)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable g) => Data.Foldable.Foldable (f Data.Generics.Fixplate.Functor.:+: g)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable g) => Data.Traversable.Traversable (f Data.Generics.Fixplate.Functor.:+: g)
instance (GHC.Base.Functor f, GHC.Base.Functor g) => GHC.Base.Functor (f Data.Generics.Fixplate.Functor.:*: g)
instance (Data.Foldable.Foldable f, Data.Foldable.Foldable g) => Data.Foldable.Foldable (f Data.Generics.Fixplate.Functor.:*: g)
instance (Data.Traversable.Traversable f, Data.Traversable.Traversable g) => Data.Traversable.Traversable (f Data.Generics.Fixplate.Functor.:*: g)
instance (Data.Generics.Fixplate.Base.EqF f, Data.Generics.Fixplate.Base.EqF g) => Data.Generics.Fixplate.Base.EqF (f Data.Generics.Fixplate.Functor.:+: g)
instance (Data.Generics.Fixplate.Base.OrdF f, Data.Generics.Fixplate.Base.OrdF g) => Data.Generics.Fixplate.Base.OrdF (f Data.Generics.Fixplate.Functor.:+: g)
instance (Data.Generics.Fixplate.Base.ShowF f, Data.Generics.Fixplate.Base.ShowF g) => Data.Generics.Fixplate.Base.ShowF (f Data.Generics.Fixplate.Functor.:+: g)
instance (Data.Generics.Fixplate.Base.EqF f, Data.Generics.Fixplate.Base.EqF g) => Data.Generics.Fixplate.Base.EqF (f Data.Generics.Fixplate.Functor.:*: g)
instance (Data.Generics.Fixplate.Base.OrdF f, Data.Generics.Fixplate.Base.OrdF g) => Data.Generics.Fixplate.Base.OrdF (f Data.Generics.Fixplate.Functor.:*: g)
instance (Data.Generics.Fixplate.Base.ShowF f, Data.Generics.Fixplate.Base.ShowF g) => Data.Generics.Fixplate.Base.ShowF (f Data.Generics.Fixplate.Functor.:*: g)


-- | Generic pretty-printing of expression trees.
--   
--   TODO:
--   
--   <ul>
--   <li>make the style configurable (so that we can print the same
--   expression in different formats) (in Haskell98, we have to use the
--   record instead of class trick for this?)</li>
--   <li>corresponding parser?</li>
--   </ul>
module Data.Generics.Fixplate.Pretty

-- | Associativity
data Assoc
NoAssoc :: Assoc
LeftAssoc :: Assoc
RightAssoc :: Assoc

-- | A pair of matching brackets, eg. <tt>Bracket "(" ")"</tt> or
--   <tt>Bracket "[|" "|]"</tt>.
data Bracket
Bracket :: !String -> !String -> Bracket

-- | A separator, eg. <tt>","</tt> or <tt>" | "</tt>.
type Separator = String

-- | Application style
data AppStyle

-- | eg. <tt>(Node arg1 arg2 arg3)</tt>; precedence will be <tt>app_prec ==
--   10</tt>
Haskell :: AppStyle

-- | eg. <tt>node[arg1,arg2,arg3]</tt>; precedence will be 11, but child
--   environment precedence will be 0
Algol :: !Bracket -> !Separator -> AppStyle

-- | Mixfix style. Example:
--   
--   <pre>
--   [ Keyword "if" , Placeholder , keyword "then" , Placeholder , keyword "else" , Placeholder ]
--   </pre>
data MixWord
Keyword :: String -> MixWord
Placeholder :: MixWord
mixWords :: [MixWord] -> [ShowS] -> ShowS

-- | Fixities. TODO: separate non-fixity stuff like style and words
data Fixity

-- | eg. <tt>variable</tt>; precedence will be 666
Atom :: Fixity

-- | eg. <tt>(Node arg1 arg2 arg3)</tt> or <tt>node[arg1,arg2,arg3]</tt>.
Application :: !AppStyle -> Fixity

-- | eg. <tt>~arg</tt>; the <tt>Int</tt> is the precendence
Prefix :: !Int -> Fixity

-- | eg. <tt>x+y</tt>
Infix :: !Assoc -> !Int -> Fixity

-- | eg. <tt>arg++</tt>
Postfix :: !Int -> Fixity

-- | eg. <tt>if ... then ... else ... </tt> or <tt>let ... in ...</tt>.
--   With precedence 0?
Mixfix :: [MixWord] -> Fixity

-- | for your custom rendering
Custom :: !Int -> Fixity
fixityPrecedence :: Fixity -> Int

-- | A class encoding fixity and rendering of nodes if the tree.
--   
--   Minimum complete definition: <a>fixity</a>, and <a>showNode</a> or
--   <a>showsPrecNode</a>. Unless you want some type of rendering not
--   directly supported, you shouldn't specify <a>showsPrecNode</a>.
class (Functor f, Foldable f) => Pretty f where showsPrecNode child d node = showParen (d > prec) $ case fty of { Atom -> showString (showNode node) Application style -> case style of { Haskell -> head . args where head = showString (showNode node) args = foldr (.) id [showChar ' ' . child (prec + 1) c | c <- children] Algol (Bracket open close) sep -> head . showString open . args . showString close where head = showString (showNode node) args = foldr (.) id $ intersperse (showString sep) [child 0 c | c <- children] } Prefix prec -> case children of { [] -> error "showsPrecNode: prefix node with no arguments" (c : cs) -> op . arg1 c . args cs } where op = showString (showNode node) arg1 c = child (prec + 1) c args cs = foldr (.) id [showChar ' ' . child (prec + 1) c | c <- cs] Postfix prec -> case children of { [] -> error "showsPrecNode: postfix node with no arguments" ccs -> let (cs, c) = (init ccs, last ccs) in args cs . arg1 c . op } where op = showString (showNode node) arg1 c = child (prec + 1) c args cs = foldr (.) id [child (prec + 1) c . showChar ' ' | c <- cs] Infix assoc prec -> case children of { [] -> error "showsPrecNode: infix node with no arguments" [_] -> error "showsPrecNode: infix node with a single argument" (c1 : c2 : cs) -> lhs c1 . op . rhs c2 . rest cs } where lhs c1 = child lprec c1 op = showString (showNode node) rhs c2 = child rprec c2 rest cs = foldr (.) id [showChar ' ' . child (prec + 1) c | c <- cs] lprec = case assoc of { LeftAssoc -> prec _ -> prec + 1 } rprec = case assoc of { RightAssoc -> prec _ -> prec + 1 } Mixfix mwords -> mixWords mwords [child (prec + 1) c | c <- children] Custom prec -> error "for custom rendering, you should redefine `showsPrecNode'" } where fty = fixity node prec = fixityPrecedence fty children = toList node

-- | fixity of the node
fixity :: Pretty f => f a -> Fixity

-- | a string representing the node <i>without</i> the children
showNode :: Pretty f => f a -> String

-- | full rendering of the node. You can redefine this for custom
--   renderings.
showsPrecNode :: Pretty f => (Int -> a -> ShowS) -> Int -> f a -> ShowS

-- | Render the expression
pretty :: Pretty f => Mu f -> String
prettyS :: Pretty f => Mu f -> ShowS
prettyPrec :: Pretty f => Int -> Mu f -> ShowS
instance GHC.Show.Show Data.Generics.Fixplate.Pretty.Fixity
instance GHC.Classes.Eq Data.Generics.Fixplate.Pretty.Fixity
instance GHC.Show.Show Data.Generics.Fixplate.Pretty.MixWord
instance GHC.Classes.Eq Data.Generics.Fixplate.Pretty.MixWord
instance GHC.Show.Show Data.Generics.Fixplate.Pretty.AppStyle
instance GHC.Classes.Eq Data.Generics.Fixplate.Pretty.AppStyle
instance GHC.Show.Show Data.Generics.Fixplate.Pretty.Bracket
instance GHC.Classes.Eq Data.Generics.Fixplate.Pretty.Bracket
instance GHC.Show.Show Data.Generics.Fixplate.Pretty.Assoc
instance GHC.Classes.Eq Data.Generics.Fixplate.Pretty.Assoc


-- | Generic hashing on trees. We recursively compute hashes of all
--   subtrees, giving fast inequality testing, and a fast, but meaningless
--   (more-or-less random) ordering on the set of trees (so that we can put
--   them into Map-s).
--   
--   The way it works is that when we compute the hash of a node, we use
--   the hashes of the children directly; this way, you can also
--   incrementally build up a hashed tree.
module Data.Generics.Fixplate.Hash

-- | Hash annotation (question: should the Hash field be strict? everything
--   else in the library is lazy...)
--   
--   This is custom datatype instead of reusing <a>Ann</a> because of the
--   different Eq/Ord instances we need.
data HashAnn hash f a
HashAnn :: hash -> (f a) -> HashAnn hash f a
getHash :: HashAnn hash f a -> hash
unHashAnn :: HashAnn hash f a -> f a

-- | A tree annotated with hashes of all subtrees. This gives us fast
--   inequality testing, and fast (but meaningless!) ordering for
--   <tt>Map</tt>-s.
type HashMu hash f = Mu (HashAnn hash f)

-- | The hash of the complete tree.
topHash :: HashMu hash f -> hash
forgetHash :: Functor f => HashMu hash f -> Mu f

-- | A concrete hash implementation. We don't use type classes since
--   
--   <ul>
--   <li>a hash type class does not belong to this library;</li>
--   <li>we don't want to restrict the user's design space</li>
--   </ul>
--   
--   Thus we simulate type classes with record types.
data HashValue hash
HashValue :: hash -> (Char -> hash -> hash) -> (hash -> hash -> hash) -> HashValue hash

-- | the hash of an empty byte sequence
[_emptyHash] :: HashValue hash -> hash

-- | digest a (unicode) character
[_hashChar] :: HashValue hash -> Char -> hash -> hash

-- | digest a hash value
[_hashHash] :: HashValue hash -> hash -> hash -> hash

-- | This function uses the <a>ShowF</a> instance to compute the hash of a
--   node; this way you always have a working version without writing any
--   additional code.
--   
--   However, you can also supply your own hash implementation (which can
--   be more efficient, for example), if you use <a>hashTreeWith</a>
--   instead.
hashTree :: (Foldable f, Functor f, ShowF f) => HashValue hash -> Mu f -> HashMu hash f
hashTreeWith :: (Foldable f, Functor f) => HashValue hash -> (f Hole -> hash -> hash) -> Mu f -> HashMu hash f

-- | Build a hashed node from the children.
hashNode :: (Foldable f, Functor f, ShowF f) => HashValue hash -> f (HashMu hash f) -> HashMu hash f
hashNodeWith :: (Foldable f, Functor f) => HashValue hash -> (f Hole -> hash -> hash) -> f (HashMu hash f) -> HashMu hash f
instance (GHC.Show.Show hash, GHC.Show.Show (f a)) => GHC.Show.Show (Data.Generics.Fixplate.Hash.HashAnn hash f a)
instance GHC.Base.Functor f => GHC.Base.Functor (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance Data.Foldable.Foldable f => Data.Foldable.Foldable (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance Data.Traversable.Traversable f => Data.Traversable.Traversable (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance (GHC.Classes.Eq hash, Data.Generics.Fixplate.Base.EqF f) => Data.Generics.Fixplate.Base.EqF (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance (GHC.Classes.Ord hash, Data.Generics.Fixplate.Base.OrdF f) => Data.Generics.Fixplate.Base.OrdF (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance (Data.Generics.Fixplate.Base.ShowF f, GHC.Show.Show hash) => Data.Generics.Fixplate.Base.ShowF (Data.Generics.Fixplate.Hash.HashAnn hash f)
instance GHC.Show.Show Data.Generics.Fixplate.Hash.Void