Copyright  (c) 20112012 Brent Yorgey 

License  BSDstyle (see LICENSE) 
Maintainer  diagramsdiscuss@googlegroups.com 
Safe Haskell  None 
Language  Haskell2010 
This module provides access to all of the internals of the DUALtree 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
nonempty trees, DUALTreeNE
, is defined, as well as the type
DUALTreeU
which represents a nonempty 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 Option
. 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.
 data DUALTreeNE d u a l
 newtype DUALTreeU d u a l = DUALTreeU {
 unDUALTreeU :: (u, DUALTreeNE d u a l)
 newtype DUALTree d u a l = DUALTree {
 unDUALTree :: Option (DUALTreeU d u a l)
 empty :: DUALTree d u a l
 leaf :: u > l > DUALTree d u a l
 leafU :: u > DUALTree d u a l
 annot :: (Semigroup u, Action d u) => a > DUALTree d u a l > DUALTree d u a l
 applyD :: (Semigroup d, Semigroup u, Action d u) => d > DUALTree d u a l > DUALTree d u a l
 applyUpre :: (Semigroup u, Action d u) => u > DUALTree d u a l > DUALTree d u a l
 applyUpost :: (Semigroup u, Action d u) => u > DUALTree d u a l > DUALTree d u a l
 mapUNE :: (u > u') > DUALTreeNE d u a l > DUALTreeNE d u' a l
 mapUU :: (u > u') > DUALTreeU d u a l > DUALTreeU d u' a l
 mapU :: (u > u') > DUALTree d u a l > DUALTree d u' a l
 nonEmpty :: DUALTree d u a l > Maybe (u, DUALTreeNE d u a l)
 getU :: DUALTree d u a l > Maybe u
 foldDUALNE :: (Semigroup d, Monoid d) => (d > l > r) > r > (NonEmpty r > r) > (d > r > r) > (a > r > r) > DUALTreeNE d u a l > r
 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
 flatten :: (Semigroup d, Monoid d) => DUALTree d u a l > [(l, d)]
DUALtrees
data DUALTreeNE d u a l Source
Nonempty DUALtrees.
Leaf u l  Leaf with data value and 
LeafU u  Leaf with only 
Concat (NonEmpty (DUALTreeU d u a l))  nway branch, containing a nonempty list of subtrees. 
Act d (DUALTreeU d u a l) 

Annot a (DUALTreeU d u a l)  Internal data value 
Typeable (* > * > * > * > *) DUALTreeNE  
Functor (DUALTreeNE d u a)  
(Eq d, Eq u, Eq a, Eq l) => Eq (DUALTreeNE d u a l)  
(Show d, Show u, Show a, Show l) => Show (DUALTreeNE d u a l)  
(Action d u, Semigroup u) => Semigroup (DUALTreeNE d u a l)  
Newtype (DUALTreeU d u a l) (u, DUALTreeNE d u a l) 
newtype DUALTreeU d u a l Source
A nonempty DUALtree paired with a cached u
value. These
should never be constructed directly; instead, use pullU
.
DUALTreeU  

Typeable (* > * > * > * > *) DUALTreeU  
Functor (DUALTreeU d u a)  
(Eq d, Eq u, Eq a, Eq l) => Eq (DUALTreeU d u a l)  
(Show d, Show u, Show a, Show l) => Show (DUALTreeU d u a l)  
(Semigroup u, Action d u) => Semigroup (DUALTreeU d u a l)  
Newtype (DUALTree d u a l) (Option (DUALTreeU d u a l))  
Newtype (DUALTreeU d u a l) (u, DUALTreeNE d u a l) 
newtype DUALTree d u a l Source
Rose (nary) trees with both upwards (i.e. cached) and
downwardstraveling (i.e. accumulating) monoidal annotations.
Abstractly, a DUALTree is a rose (nary) 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 thatfmap
of course cannot alter anyu
annotations.Semigroup
.DUALTreeNE
s form a semigroup where(<>)
corresponds to adjoining two trees under a common parent root, withsconcat
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 underflatten
. Technically usingfoldDUAL
directly enables one to observe the difference, but it is understood thatfoldDUAL
should be used only in ways such that reassociation of subtrees "does not matter".Monoid
. The identity is the empty tree.
DUALTree  

Typeable (* > * > * > * > *) DUALTree  
Functor (DUALTree d u a)  
(Eq d, Eq u, Eq a, Eq l) => Eq (DUALTree d u a l)  
(Show d, Show u, Show a, Show l) => Show (DUALTree d u a l)  
(Semigroup u, Action d u) => Monoid (DUALTree d u a l)  
(Semigroup u, Action d u) => Semigroup (DUALTree d u a l)  
Newtype (DUALTree d u a l) (Option (DUALTreeU d u a l)) 
Constructing DUALtrees
empty :: DUALTree d u a l Source
The empty DUALtree. This is a synonym for mempty
, but with a
more general type.
leaf :: u > l > DUALTree d u a l Source
Construct a leaf node from a u
annotation along with a leaf
datum.
annot :: (Semigroup u, Action d u) => a > DUALTree d u a l > DUALTree d u a l Source
Add an internal data value at the root of a tree. Note that this only works on nonempty trees; on empty trees this function is the identity.
applyD :: (Semigroup d, Semigroup u, Action d u) => d > DUALTree d u a l > DUALTree d u a l Source
Apply a d
annotation at the root of a tree, transforming all
u
annotations by the action of d
.
Modifying DUALtrees
applyUpre :: (Semigroup u, Action d u) => u > DUALTree d u a l > DUALTree d u a l Source
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
applyUpost :: (Semigroup u, Action d u) => u > DUALTree d u a l > DUALTree d u a l Source
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
mapUNE :: (u > u') > DUALTreeNE d u a l > DUALTreeNE d u' a l Source
Map a function (which must be a monoid homomorphism, and commute
with the action of d
) over all the u
annotations in a nonempty
DUALtree.
mapUU :: (u > u') > DUALTreeU d u a l > DUALTreeU d u' a l Source
Map a function (which must be a monoid homomorphism, and commute
with the action of d
) over all the u
annotations in a
nonempty DUALtree paired with its cached u
value.
mapU :: (u > u') > DUALTree d u a l > DUALTree d u' a l Source
Map a function over all the u
annotations in a DUALtree. 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)
Accessors and eliminators
nonEmpty :: DUALTree d u a l > Maybe (u, DUALTreeNE d u a l) Source
Decompose a DUALtree into either Nothing
(if empty) or a
toplevel cached u
annotation paired with a nonempty
DUALtree.
getU :: DUALTree d u a l > Maybe u Source
Get the u
annotation at the root, or Nothing
if the tree is
empty.
:: (Semigroup d, Monoid d)  
=> (d > l > r)  Process a leaf datum along with the
accumulation of 
> r  Replace 
> (NonEmpty r > r)  Combine results at a branch node 
> (d > r > r)  Process an internal d node 
> (a > r > r)  Process an internal datum 
> DUALTreeNE d u a l  
> r 
Fold for nonempty DUALtrees.
:: (Semigroup d, Monoid d)  
=> (d > l > r)  Process a leaf datum along with the
accumulation of 
> r  Replace 
> (NonEmpty r > r)  Combine results at a branch node 
> (d > r > r)  Process an internal d node 
> (a > r > r)  Process an internal datum 
> DUALTree d u a l  
> Maybe r 
Fold for DUALtrees. 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.