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


-- | Rose trees with cached and accumulating monoidal annotations
--   
--   Rose (n-ary) trees with both upwards- (<i>i.e.</i> cached) and
--   downwards-traveling (<i>i.e.</i> accumulating) monoidal annotations.
--   This is used as the core data structure underlying the
--   <tt>diagrams</tt> framework
--   (<a>http://projects.haskell.org/diagrams</a>), but potentially has
--   other applications as well.
--   
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   <tt>l</tt>) at leaves, data (of type <tt>a</tt>) at internal nodes,
--   and two types of monoidal annotations, one (of type <tt>u</tt>)
--   travelling "up" the tree and one (of type <tt>d</tt>) traveling
--   "down".
--   
--   See <a>Data.Tree.DUAL</a> for full documentation.
--   <a>Data.Tree.DUAL</a> provides a public API which should suffice for
--   most purposes. <a>Data.Tree.DUAL.Internal</a> exports more of the
--   internal implementation---use it at your own risk.
@package dual-tree
@version 0.1.0.4


-- | This module provides access to all of the internals of the DUAL-tree
--   implementation. Depend on the internals at your own risk! For a safe
--   public API (and complete documentation), see <a>Data.Tree.DUAL</a>.
--   
--   The main things exported by this module which are not exported from
--   <a>Data.Tree.DUAL</a> are two extra types used in the implementation
--   of <a>DUALTree</a>, along with functions for manipulating them. A type
--   of <i>non-empty</i> trees, <a>DUALTreeNE</a>, is defined, as well as
--   the type <a>DUALTreeU</a> which represents a non-empty tree paired
--   with a cached <tt>u</tt> annotation. <a>DUALTreeNE</a> and
--   <a>DUALTreeU</a> are mutually recursive, so that recursive tree nodes
--   are interleaved with cached <tt>u</tt> annotations. <a>DUALTree</a> is
--   defined by just wrapping <a>DUALTreeU</a> in <a>Option</a>. This
--   method has the advantage that the type system enforces the invariant
--   that there is only one representation for the empty tree. It also
--   allows us to get away with only <a>Semigroup</a> constraints in many
--   places.
module Data.Tree.DUAL.Internal

-- | <i>Non-empty</i> DUAL-trees.
data DUALTreeNE d u a l

-- | Leaf with data value and <tt>u</tt> annotation
Leaf :: u -> l -> DUALTreeNE d u a l

-- | Leaf with only <tt>u</tt> annotation
LeafU :: u -> DUALTreeNE d u a l

-- | n-way branch, containing a <i>non-empty</i> list of subtrees.
Concat :: (NonEmpty (DUALTreeU d u a l)) -> DUALTreeNE d u a l

-- | <tt>d</tt> annotation
Act :: d -> (DUALTreeU d u a l) -> DUALTreeNE d u a l

-- | Internal data value
Annot :: a -> (DUALTreeU d u a l) -> DUALTreeNE d u a l

-- | A non-empty DUAL-tree paired with a cached <tt>u</tt> value. These
--   should never be constructed directly; instead, use <a>pullU</a>.
newtype DUALTreeU d u a l
DUALTreeU :: (u, DUALTreeNE d u a l) -> DUALTreeU d u a l
unDUALTreeU :: DUALTreeU d u a l -> (u, DUALTreeNE d u a l)

-- | Rose (n-ary) trees with both upwards- (<i>i.e.</i> cached) and
--   downwards-traveling (<i>i.e.</i> accumulating) monoidal annotations.
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   <tt>l</tt>) at leaves, data (of type <tt>a</tt>) at internal nodes,
--   and two types of monoidal annotations, one (of type <tt>u</tt>)
--   travelling "up" the tree and one (of type <tt>d</tt>) traveling
--   "down". See the documentation at the top of this file for full
--   details.
--   
--   <tt>DUALTree</tt> comes with some instances:
--   
--   <ul>
--   <li><a>Functor</a>, for modifying leaf data. Note that <a>fmap</a> of
--   course cannot alter any <tt>u</tt> annotations.</li>
--   <li><a>Semigroup</a>. <tt>DUALTreeNE</tt>s form a semigroup where
--   <tt>(&lt;&gt;)</tt> corresponds to adjoining two trees under a common
--   parent root, with <tt>sconcat</tt> specialized to put all the trees
--   under a single parent. Note that this does not satisfy associativity
--   up to structural equality, but only up to observational equivalence
--   under <a>flatten</a>. Technically using <a>foldDUAL</a> directly
--   enables one to observe the difference, but it is understood that
--   <a>foldDUAL</a> should be used only in ways such that reassociation of
--   subtrees "does not matter".</li>
--   <li><a>Monoid</a>. The identity is the empty tree.</li>
--   </ul>
newtype DUALTree d u a l
DUALTree :: Option (DUALTreeU d u a l) -> DUALTree d u a l
unDUALTree :: DUALTree d u a l -> Option (DUALTreeU d u a l)

-- | The empty DUAL-tree. This is a synonym for <a>mempty</a>, but with a
--   more general type.
empty :: DUALTree d u a l

-- | Construct a leaf node from a <tt>u</tt> annotation along with a leaf
--   datum.
leaf :: u -> l -> DUALTree d u a l

-- | Construct a leaf node from a <tt>u</tt> annotation.
leafU :: u -> DUALTree d u a l

-- | Add an internal data value at the root of a tree. Note that this only
--   works on <i>non-empty</i> trees; on empty trees this function is the
--   identity.
annot :: (Semigroup u, Action d u) => a -> DUALTree d u a l -> DUALTree d u a l

-- | Apply a <tt>d</tt> annotation at the root of a tree, transforming all
--   <tt>u</tt> annotations by the action of <tt>d</tt>.
applyD :: (Semigroup d, Semigroup u, Action d u) => d -> DUALTree d u a l -> DUALTree d u a l

-- | Add a <tt>u</tt> annotation to the root, combining it (on the left)
--   with the existing cached <tt>u</tt> annotation. This function is
--   provided just for convenience; <tt>applyUpre u t = <a>leafU</a> u
--   &lt;&gt; t</tt>.
applyUpre :: (Semigroup u, Action d u) => u -> DUALTree d u a l -> DUALTree d u a l

-- | Add a <tt>u</tt> annotation to the root, combining it (on the right)
--   with the existing cached <tt>u</tt> annotation. This function is
--   provided just for convenience; <tt>applyUpost u t = t &lt;&gt;
--   <a>leafU</a> u</tt>.
applyUpost :: (Semigroup u, Action d u) => u -> DUALTree d u a l -> DUALTree d u a l

-- | Map a function (which must be a monoid homomorphism, and commute with
--   the action of <tt>d</tt>) over all the <tt>u</tt> annotations in a
--   non-empty DUAL-tree.
mapUNE :: (u -> u') -> DUALTreeNE d u a l -> DUALTreeNE d u' a l

-- | Map a function (which must be a monoid homomorphism, and commute with
--   the action of <tt>d</tt>) over all the <tt>u</tt> annotations in a
--   non-empty DUAL-tree paired with its cached <tt>u</tt> value.
mapUU :: (u -> u') -> DUALTreeU d u a l -> DUALTreeU d u' a l

-- | Map a function over all the <tt>u</tt> annotations in a DUAL-tree. The
--   function must be a monoid homomorphism, and must commute with the
--   action of <tt>d</tt> on <tt>u</tt>. That is, to use <tt>mapU f</tt>
--   safely it must be the case that
--   
--   <ul>
--   <li><pre>f mempty == mempty</pre></li>
--   <li><pre>f (u1 &lt;&gt; u2) == f u1 &lt;&gt; f u2</pre></li>
--   <li><pre>f (act d u) == act d (f u)</pre></li>
--   </ul>
mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l

-- | Decompose a DUAL-tree into either <tt>Nothing</tt> (if empty) or a
--   top-level cached <tt>u</tt> annotation paired with a non-empty
--   DUAL-tree.
nonEmpty :: DUALTree d u a l -> Maybe (u, DUALTreeNE d u a l)

-- | Get the <tt>u</tt> annotation at the root, or <tt>Nothing</tt> if the
--   tree is empty.
getU :: DUALTree d u a l -> Maybe u

-- | Fold for non-empty DUAL-trees.
foldDUALNE :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (a -> r -> r) -> DUALTreeNE d u a l -> r

-- | Fold for DUAL-trees. It is given access to the internal and leaf data,
--   and the accumulated <tt>d</tt> values at each leaf. It is also allowed
--   to replace "<tt>u</tt>-only" leaves with a constant value. In
--   particular, however, it is <i>not</i> given access to any of the
--   <tt>u</tt> annotations, the idea being that those are used only for
--   <i>constructing</i> trees. It is also not given access to <tt>d</tt>
--   values as they occur in the tree, only as they accumulate at leaves.
--   If you do need access to <tt>u</tt> or <tt>d</tt> values, you can
--   duplicate the values you need in the internal data nodes.
--   
--   The result is <tt>Nothing</tt> if and only if the tree is empty.
foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (a -> r -> r) -> DUALTree d u a l -> Maybe r

-- | A specialized fold provided for convenience: flatten a tree into a
--   list of leaves along with their <tt>d</tt> annotations, ignoring
--   internal data values.
flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)]
instance Typeable4 DUALTreeU
instance Typeable4 DUALTreeNE
instance Typeable4 DUALTree
instance Functor (DUALTreeU d u a)
instance (Semigroup u, Action d u) => Semigroup (DUALTreeU d u a l)
instance (Show d, Show u, Show a, Show l) => Show (DUALTreeU d u a l)
instance (Eq d, Eq u, Eq a, Eq l) => Eq (DUALTreeU d u a l)
instance Functor (DUALTreeNE d u a)
instance (Show d, Show u, Show a, Show l) => Show (DUALTreeNE d u a l)
instance (Eq d, Eq u, Eq a, Eq l) => Eq (DUALTreeNE d u a l)
instance Functor (DUALTree d u a)
instance (Semigroup u, Action d u) => Semigroup (DUALTree d u a l)
instance (Show d, Show u, Show a, Show l) => Show (DUALTree d u a l)
instance (Eq d, Eq u, Eq a, Eq l) => Eq (DUALTree d u a l)
instance (Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTree d u a l)
instance (Semigroup u, Action d u) => Monoid (DUALTree d u a l)
instance Newtype (DUALTree d u a l) (Option (DUALTreeU d u a l))
instance (Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTreeU d u a l)
instance Newtype (DUALTreeU d u a l) (u, DUALTreeNE d u a l)
instance (Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTreeNE d u a l)
instance Newtype (DAct d) d
instance (Action d u, Semigroup u) => Semigroup (DUALTreeNE d u a l)


-- | Rose (n-ary) trees with both upwards- (<i>i.e.</i> cached) and
--   downwards-traveling (<i>i.e.</i> accumulating) monoidal annotations.
--   This is used as the core data structure underlying the
--   <tt>diagrams</tt> framework
--   (<a>http://projects.haskell.org/diagrams</a>), but potentially has
--   other applications as well.
--   
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   <tt>l</tt>) at leaves, data (of type <tt>a</tt>) at internal nodes,
--   and two types of monoidal annotations, one (of type <tt>u</tt>)
--   travelling "up" the tree and one (of type <tt>d</tt>) traveling
--   "down".
--   
--   Specifically, there are five types of nodes:
--   
--   <ul>
--   <li>Leaf nodes which contain a data value of type <tt>l</tt> and an
--   annotation of type <tt>u</tt>. The annotation represents information
--   about a tree that should be accumulated (<i>e.g.</i> number of leaves,
--   some sort of "weight", <i>etc.</i>). If you are familiar with finger
--   trees (<a>http://www.soi.city.ac.uk/~ross/papers/FingerTree.html</a>,
--   <a>http://hackage.haskell.org/package/fingertree</a>), it is the same
--   idea.</li>
--   <li>There is also a special type of leaf node which contains only a
--   <tt>u</tt> value, and no data. This allows cached <tt>u</tt> values to
--   be "modified" by inserting extra annotations.</li>
--   <li>Branch nodes, containing a list of subtrees.</li>
--   <li>Internal nodes with a value of type <tt>d</tt>. <tt>d</tt> may
--   have an <i>action</i> on <tt>u</tt> (see the <tt>Action</tt> type
--   class, defined in <a>Data.Monoid.Action</a> from the
--   <tt>monoid-extras</tt> package). Semantically speaking, applying a
--   <tt>d</tt> annotation to a tree transforms all the <tt>u</tt>
--   annotations below it by acting on them. Operationally, however, since
--   the action must be a monoid homomorphism, applying a <tt>d</tt>
--   annotation can actually be done in constant time.</li>
--   <li>Internal nodes with data values of type <tt>a</tt>, possibly of a
--   different type than those in the leaves. These are just "along for the
--   ride" and are unaffected by <tt>u</tt> and <tt>d</tt>
--   annotations.</li>
--   </ul>
--   
--   There are two critical points to note about <tt>u</tt> and <tt>d</tt>
--   annotations:
--   
--   <ul>
--   <li>The combined <tt>u</tt> annotation for an entire tree is always
--   cached at the root and available in constant (amortized) time.</li>
--   <li>The <tt>mconcat</tt> of all the <tt>d</tt> annotations along the
--   path from the root to each leaf is available along with the leaf
--   during a fold operation.</li>
--   </ul>
--   
--   A fold over a <tt>DUALTree</tt> is given access to the internal and
--   leaf data, and the accumulated <tt>d</tt> values at each leaf. It is
--   also allowed to replace "<tt>u</tt>-only" leaves with a constant
--   value. In particular, however, it is <i>not</i> given access to any of
--   the <tt>u</tt> annotations, the idea being that those are used only
--   for <i>constructing</i> trees. It is also not given access to
--   <tt>d</tt> values as they occur in the tree, only as they accumulate
--   at leaves. If you do need access to <tt>u</tt> or <tt>d</tt> values,
--   you can duplicate the values you need in the internal data nodes.
module Data.Tree.DUAL

-- | Rose (n-ary) trees with both upwards- (<i>i.e.</i> cached) and
--   downwards-traveling (<i>i.e.</i> accumulating) monoidal annotations.
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   <tt>l</tt>) at leaves, data (of type <tt>a</tt>) at internal nodes,
--   and two types of monoidal annotations, one (of type <tt>u</tt>)
--   travelling "up" the tree and one (of type <tt>d</tt>) traveling
--   "down". See the documentation at the top of this file for full
--   details.
--   
--   <tt>DUALTree</tt> comes with some instances:
--   
--   <ul>
--   <li><a>Functor</a>, for modifying leaf data. Note that <a>fmap</a> of
--   course cannot alter any <tt>u</tt> annotations.</li>
--   <li><a>Semigroup</a>. <tt>DUALTreeNE</tt>s form a semigroup where
--   <tt>(&lt;&gt;)</tt> corresponds to adjoining two trees under a common
--   parent root, with <tt>sconcat</tt> specialized to put all the trees
--   under a single parent. Note that this does not satisfy associativity
--   up to structural equality, but only up to observational equivalence
--   under <a>flatten</a>. Technically using <a>foldDUAL</a> directly
--   enables one to observe the difference, but it is understood that
--   <a>foldDUAL</a> should be used only in ways such that reassociation of
--   subtrees "does not matter".</li>
--   <li><a>Monoid</a>. The identity is the empty tree.</li>
--   </ul>
data DUALTree d u a l

-- | The empty DUAL-tree. This is a synonym for <a>mempty</a>, but with a
--   more general type.
empty :: DUALTree d u a l

-- | Construct a leaf node from a <tt>u</tt> annotation along with a leaf
--   datum.
leaf :: u -> l -> DUALTree d u a l

-- | Construct a leaf node from a <tt>u</tt> annotation.
leafU :: u -> DUALTree d u a l

-- | Add an internal data value at the root of a tree. Note that this only
--   works on <i>non-empty</i> trees; on empty trees this function is the
--   identity.
annot :: (Semigroup u, Action d u) => a -> DUALTree d u a l -> DUALTree d u a l

-- | Apply a <tt>d</tt> annotation at the root of a tree, transforming all
--   <tt>u</tt> annotations by the action of <tt>d</tt>.
applyD :: (Semigroup d, Semigroup u, Action d u) => d -> DUALTree d u a l -> DUALTree d u a l

-- | Add a <tt>u</tt> annotation to the root, combining it (on the left)
--   with the existing cached <tt>u</tt> annotation. This function is
--   provided just for convenience; <tt>applyUpre u t = <a>leafU</a> u
--   &lt;&gt; t</tt>.
applyUpre :: (Semigroup u, Action d u) => u -> DUALTree d u a l -> DUALTree d u a l

-- | Add a <tt>u</tt> annotation to the root, combining it (on the right)
--   with the existing cached <tt>u</tt> annotation. This function is
--   provided just for convenience; <tt>applyUpost u t = t &lt;&gt;
--   <a>leafU</a> u</tt>.
applyUpost :: (Semigroup u, Action d u) => u -> DUALTree d u a l -> DUALTree d u a l

-- | Map a function over all the <tt>u</tt> annotations in a DUAL-tree. The
--   function must be a monoid homomorphism, and must commute with the
--   action of <tt>d</tt> on <tt>u</tt>. That is, to use <tt>mapU f</tt>
--   safely it must be the case that
--   
--   <ul>
--   <li><pre>f mempty == mempty</pre></li>
--   <li><pre>f (u1 &lt;&gt; u2) == f u1 &lt;&gt; f u2</pre></li>
--   <li><pre>f (act d u) == act d (f u)</pre></li>
--   </ul>
mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l

-- | Get the <tt>u</tt> annotation at the root, or <tt>Nothing</tt> if the
--   tree is empty.
getU :: DUALTree d u a l -> Maybe u

-- | Fold for DUAL-trees. It is given access to the internal and leaf data,
--   and the accumulated <tt>d</tt> values at each leaf. It is also allowed
--   to replace "<tt>u</tt>-only" leaves with a constant value. In
--   particular, however, it is <i>not</i> given access to any of the
--   <tt>u</tt> annotations, the idea being that those are used only for
--   <i>constructing</i> trees. It is also not given access to <tt>d</tt>
--   values as they occur in the tree, only as they accumulate at leaves.
--   If you do need access to <tt>u</tt> or <tt>d</tt> values, you can
--   duplicate the values you need in the internal data nodes.
--   
--   The result is <tt>Nothing</tt> if and only if the tree is empty.
foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (a -> r -> r) -> DUALTree d u a l -> Maybe r

-- | A specialized fold provided for convenience: flatten a tree into a
--   list of leaves along with their <tt>d</tt> annotations, ignoring
--   internal data values.
flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)]
