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

-- | 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 Data.Tree.DUAL.
--   
--   The main things exported by this module which are not exported from
--   Data.Tree.DUAL are two extra types used in the implementation
--   of DUALTree, along with functions for manipulating them. A type
--   of non-empty trees, DUALTreeNE, is defined, as well as
--   the type DUALTreeU which represents a non-empty tree paired
--   with a cached u annotation. DUALTreeNE and
--   DUALTreeU are mutually recursive, so that recursive tree nodes
--   are interleaved with cached u annotations. DUALTree is
--   defined by just wrapping DUALTreeU in 'Maybe. 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 Semigroup constraints in many places.
module Data.Tree.DUAL.Internal

-- | Non-empty DUAL-trees.
data DUALTreeNE d u a l

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

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

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

-- | d 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 u value. These
--   should never be constructed directly; instead, use pullU.
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.e. cached) and
--   downwards-traveling (i.e. accumulating) monoidal annotations.
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   l) at leaves, data (of type a) at internal nodes,
--   and two types of monoidal annotations, one (of type u)
--   travelling "up" the tree and one (of type d) traveling
--   "down". See the documentation at the top of this file for full
--   details.
--   
--   DUALTree comes with some instances:
--   
--   
--   
- Functor, for modifying leaf data. Note that fmap of
--   course cannot alter any u annotations.
--   
- Semigroup. DUALTreeNEs form a semigroup where
--   (<>) corresponds to adjoining two trees under a common
--   parent root, with sconcat 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 flatten. Technically using foldDUAL directly
--   enables one to observe the difference, but it is understood that
--   foldDUAL should be used only in ways such that reassociation of
--   subtrees "does not matter".
--   
- Monoid. The identity is the empty tree.
--   
newtype DUALTree d u a l
DUALTree :: Maybe (DUALTreeU d u a l) -> DUALTree d u a l
[unDUALTree] :: DUALTree d u a l -> Maybe (DUALTreeU d u a l)

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

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

-- | Construct a leaf node from a u 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 non-empty 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 d annotation at the root of a tree, transforming all
--   u annotations by the action of d.
applyD :: (Semigroup d, Semigroup u, Action d u) => d -> DUALTree d u a l -> DUALTree d u a l

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

-- | Add a u annotation to the root, combining it (on the right)
--   with the existing cached u annotation. This function is
--   provided just for convenience; applyUpost u t = t <>
--   leafU u.
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 d) over all the u 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 d) over all the u annotations in a
--   non-empty DUAL-tree paired with its cached u value.
mapUU :: (u -> u') -> DUALTreeU d u a l -> DUALTreeU d u' a l

-- | Map a function over all the u annotations in a DUAL-tree. The
--   function must be a monoid homomorphism, and must commute with the
--   action of d on u. That is, to use mapU f
--   safely it must be the case that
--   
--   
--   
- 
f mempty == mempty

--   
- 
f (u1 <> u2) == f u1 <> f u2

--   
- 
f (act d u) == act d (f u)

--   
mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l

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

-- | Get the u annotation at the root, or Nothing 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) -> (d -> 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,
--   internal d values, and the accumulated d values at
--   each leaf. It is also allowed to replace "u-only" leaves with
--   a constant value. In particular, however, it is not given
--   access to any of the u annotations, the idea being that those
--   are used only for constructing trees. If you do need access to
--   u values, you can duplicate the values you need in the
--   internal data nodes.
--   
--   Be careful not to mix up the d values at internal nodes with
--   the d values at leaves. Each d value at a leaf
--   satisfies the property that it is the mconcat of all internal
--   d values along the path from the root to the leaf.
--   
--   The result is Nothing if and only if the tree is empty.
foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (d -> 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 d annotations, ignoring
--   internal data values.
flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)]
instance (GHC.Internal.Base.Semigroup d, GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => Data.Monoid.Action.Action (Data.Tree.DUAL.Internal.DAct d) (Data.Tree.DUAL.Internal.DUALTree d u a l)
instance (GHC.Internal.Base.Semigroup d, GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => Data.Monoid.Action.Action (Data.Tree.DUAL.Internal.DAct d) (Data.Tree.DUAL.Internal.DUALTreeNE d u a l)
instance (GHC.Internal.Base.Semigroup d, GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => Data.Monoid.Action.Action (Data.Tree.DUAL.Internal.DAct d) (Data.Tree.DUAL.Internal.DUALTreeU d u a l)
instance (GHC.Classes.Eq u, GHC.Classes.Eq l, GHC.Classes.Eq d, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Tree.DUAL.Internal.DUALTree d u a l)
instance (GHC.Classes.Eq l, GHC.Classes.Eq u, GHC.Classes.Eq d, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Tree.DUAL.Internal.DUALTreeNE d u a l)
instance (GHC.Classes.Eq u, GHC.Classes.Eq l, GHC.Classes.Eq d, GHC.Classes.Eq a) => GHC.Classes.Eq (Data.Tree.DUAL.Internal.DUALTreeU d u a l)
instance GHC.Internal.Base.Functor (Data.Tree.DUAL.Internal.DUALTree d u a)
instance GHC.Internal.Base.Functor (Data.Tree.DUAL.Internal.DUALTreeNE d u a)
instance GHC.Internal.Base.Functor (Data.Tree.DUAL.Internal.DUALTreeU d u a)
instance (GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => GHC.Internal.Base.Monoid (Data.Tree.DUAL.Internal.DUALTree d u a l)
instance (GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => GHC.Internal.Base.Semigroup (Data.Tree.DUAL.Internal.DUALTree d u a l)
instance (Data.Monoid.Action.Action d u, GHC.Internal.Base.Semigroup u) => GHC.Internal.Base.Semigroup (Data.Tree.DUAL.Internal.DUALTreeNE d u a l)
instance (GHC.Internal.Base.Semigroup u, Data.Monoid.Action.Action d u) => GHC.Internal.Base.Semigroup (Data.Tree.DUAL.Internal.DUALTreeU d u a l)
instance (GHC.Internal.Show.Show u, GHC.Internal.Show.Show l, GHC.Internal.Show.Show d, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.Tree.DUAL.Internal.DUALTree d u a l)
instance (GHC.Internal.Show.Show l, GHC.Internal.Show.Show u, GHC.Internal.Show.Show d, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.Tree.DUAL.Internal.DUALTreeNE d u a l)
instance (GHC.Internal.Show.Show u, GHC.Internal.Show.Show l, GHC.Internal.Show.Show d, GHC.Internal.Show.Show a) => GHC.Internal.Show.Show (Data.Tree.DUAL.Internal.DUALTreeU d u a l)

-- | Rose (n-ary) trees with both upwards- (i.e. cached) and
--   downwards-traveling (i.e. accumulating) monoidal annotations.
--   This is used as the core data structure underlying the
--   diagrams framework (https://diagrams.github.io), but
--   potentially has other applications as well.
--   
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   l) at leaves, data (of type a) at internal nodes,
--   and two types of monoidal annotations, one (of type u)
--   travelling "up" the tree and one (of type d) traveling
--   "down".
--   
--   Specifically, there are five types of nodes:
--   
--   
--   
- Leaf nodes which contain a data value of type l and an
--   annotation of type u. The annotation represents information
--   about a tree that should be accumulated (e.g. number of leaves,
--   some sort of "weight", etc.). If you are familiar with finger
--   trees (http://www.soi.city.ac.uk/~ross/papers/FingerTree.html,
--   http://hackage.haskell.org/package/fingertree), it is the same
--   idea.
--   
- There is also a special type of leaf node which contains only a
--   u value, and no data. This allows cached u values to
--   be "modified" by inserting extra annotations.
--   
- Branch nodes, containing a list of subtrees.
--   
- Internal nodes with a value of type d. d may
--   have an action on u (see the Action type
--   class, defined in Data.Monoid.Action from the
--   monoid-extras package). Semantically speaking, applying a
--   d annotation to a tree transforms all the u
--   annotations below it by acting on them. Operationally, however, since
--   the action must be a monoid homomorphism, applying a d
--   annotation can actually be done in constant time.
--   
- Internal nodes with data values of type a, possibly of a
--   different type than those in the leaves. These are just "along for the
--   ride" and are unaffected by u and d
--   annotations.
--   
--   
--   There are two critical points to note about u and d
--   annotations:
--   
--   
--   
- The combined u annotation for an entire tree is always
--   cached at the root and available in constant (amortized) time.
--   
- The mconcat of all the d annotations along the
--   path from the root to each leaf is available along with the leaf
--   during a fold operation.
--   
--   
--   A fold over a DUALTree is given access to the internal and
--   leaf data, and the accumulated d values at each leaf. It is
--   also allowed to replace "u-only" leaves with a constant
--   value. In particular, however, it is not given access to any of
--   the u annotations, the idea being that those are used only
--   for constructing trees. It is also not given access to
--   d values as they occur in the tree, only as they accumulate
--   at leaves. If you do need access to u or d 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.e. cached) and
--   downwards-traveling (i.e. accumulating) monoidal annotations.
--   Abstractly, a DUALTree is a rose (n-ary) tree with data (of type
--   l) at leaves, data (of type a) at internal nodes,
--   and two types of monoidal annotations, one (of type u)
--   travelling "up" the tree and one (of type d) traveling
--   "down". See the documentation at the top of this file for full
--   details.
--   
--   DUALTree comes with some instances:
--   
--   
--   
- Functor, for modifying leaf data. Note that fmap of
--   course cannot alter any u annotations.
--   
- Semigroup. DUALTreeNEs form a semigroup where
--   (<>) corresponds to adjoining two trees under a common
--   parent root, with sconcat 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 flatten. Technically using foldDUAL directly
--   enables one to observe the difference, but it is understood that
--   foldDUAL should be used only in ways such that reassociation of
--   subtrees "does not matter".
--   
- Monoid. The identity is the empty tree.
--   
data DUALTree d u a l

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

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

-- | Construct a leaf node from a u 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 non-empty 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 d annotation at the root of a tree, transforming all
--   u annotations by the action of d.
applyD :: (Semigroup d, Semigroup u, Action d u) => d -> DUALTree d u a l -> DUALTree d u a l

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

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

-- | Map a function over all the u annotations in a DUAL-tree. The
--   function must be a monoid homomorphism, and must commute with the
--   action of d on u. That is, to use mapU f
--   safely it must be the case that
--   
--   
--   
- 
f mempty == mempty

--   
- 
f (u1 <> u2) == f u1 <> f u2

--   
- 
f (act d u) == act d (f u)

--   
mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l

-- | Get the u annotation at the root, or Nothing 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,
--   internal d values, and the accumulated d values at
--   each leaf. It is also allowed to replace "u-only" leaves with
--   a constant value. In particular, however, it is not given
--   access to any of the u annotations, the idea being that those
--   are used only for constructing trees. If you do need access to
--   u values, you can duplicate the values you need in the
--   internal data nodes.
--   
--   Be careful not to mix up the d values at internal nodes with
--   the d values at leaves. Each d value at a leaf
--   satisfies the property that it is the mconcat of all internal
--   d values along the path from the root to the leaf.
--   
--   The result is Nothing if and only if the tree is empty.
foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (d -> 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 d annotations, ignoring
--   internal data values.
flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)]
