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


-- | Compositional Data Types on DAGs
--   
@package compdata-dags
@version 0.2


-- | This module implements a representation of directed acyclic graphs
--   (DAGs) as compact representations of trees (or <a>Term</a>s).
module Data.Comp.Dag

-- | The type of directed acyclic graphs (DAGs). <a>Dag</a>s are used as a
--   compact representation of <a>Term</a>s.
data Dag f

-- | Turn a term into a graph without sharing.
termTree :: Functor f => Term f -> Dag f

-- | This function takes a term, and returns a <a>Dag</a> with the implicit
--   sharing of the input data structure made explicit. If the sharing
--   structure of the term is cyclic an exception of type
--   <a>CyclicException</a> is thrown.
reifyDag :: Traversable f => Term f -> IO (Dag f)

-- | This function unravels a given graph to the term it represents.
unravel :: Functor f => Dag f -> Term f

-- | Checks whether two dags are bisimilar. In particular, we have the
--   following equality
--   
--   <pre>
--   bisim g1 g2 = (unravel g1 == unravel g2)
--   </pre>
--   
--   That is, two dags are bisimilar iff they have the same unravelling.
bisim :: (EqF f, Functor f, Foldable f) => Dag f -> Dag f -> Bool

-- | Checks whether the two given DAGs are isomorphic.
iso :: (Traversable f, Foldable f, EqF f) => Dag f -> Dag f -> Bool

-- | Checks whether the two given DAGs are strongly isomorphic, i.e. their
--   internal representation is the same modulo renaming of nodes.
strongIso :: (Functor f, Foldable f, EqF f) => Dag f -> Dag f -> Bool
instance Typeable CyclicException
instance Show CyclicException
instance Exception CyclicException
instance (ShowF f, Functor f) => Show (Dag f)


-- | This module implements recursion schemes derived from attribute
--   grammars. The variant implemented in this module, called parametric
--   attribute grammars, generalises both attribute grammars and attribute
--   grammars with rewrite function (as implemented in
--   <a>Data.Comp.AG</a>).
module Data.Comp.PAG

-- | This function runs a parametric attribute grammar on a term. The
--   result is the (combined) synthesised attribute at the root of the
--   term.
runPAG :: (Traversable f, Functor g, Functor d, Functor u) => Syn' f (u :*: d) u g -> Inh' f (u :*: d) d g -> (forall a. u a -> d (Context g a)) -> Term f -> u (Term g)


-- | This module implements the recursion schemes from module
--   <a>Data.Comp.PAG</a> on <a>Dag</a>s. In order to deal with the sharing
--   present in <a>Dag</a>s, the recursion schemes additionally take an
--   argument of type <tt>d -&gt; d -&gt; d</tt> that resolves clashing
--   inherited attribute values.
module Data.Comp.Dag.PAG

-- | This function runs an attribute grammar on a dag. The result is the
--   (combined) synthesised attribute at the root of the dag.
runPAG :: (Traversable f, Traversable d, Traversable g, Traversable u) => (forall a. d a -> d a -> d a) -> Syn' f (u :*: d) u g -> Inh' f (u :*: d) d g -> (forall a. u a -> d (Context g a)) -> Dag f -> u (Dag g)


-- | This module implements the recursion schemes from module
--   <a>Data.Comp.AG</a> on <a>Dag</a>s. In order to deal with the sharing
--   present in <a>Dag</a>s, the recursion schemes additionally take an
--   argument of type <tt>d -&gt; d -&gt; d</tt> that resolves clashing
--   inherited attribute values.
module Data.Comp.Dag.AG

-- | This function runs an attribute grammar on a dag. The result is the
--   (combined) synthesised attribute at the root of the dag.
runAG :: Traversable f => (d -> d -> d) -> Syn' f (u, d) u -> Inh' f (u, d) d -> (u -> d) -> Dag f -> u

-- | This function runs an attribute grammar with rewrite function on a
--   dag. The result is the (combined) synthesised attribute at the root of
--   the dag and the rewritten dag.
runRewrite :: (Traversable f, Traversable g) => (d -> d -> d) -> Syn' f (u, d) u -> Inh' f (u, d) d -> Rewrite f (u, d) g -> (u -> d) -> Dag f -> (u, Dag g)


-- | This module implements recursion schemes derived from attribute
--   grammars.
module Data.Comp.AG

-- | This function runs an attribute grammar on a term. The result is the
--   (combined) synthesised attribute at the root of the term.
runAG :: Traversable f => Syn' f (u, d) u -> Inh' f (u, d) d -> (u -> d) -> Term f -> u

-- | This function runs an attribute grammar with rewrite function on a
--   term. The result is the (combined) synthesised attribute at the root
--   of the term and the rewritten term.
runRewrite :: (Traversable f, Functor g) => Syn' f (u, d) u -> Inh' f (u, d) d -> Rewrite f (u, d) g -> (u -> d) -> Term f -> (u, Term g)