Maintainer  diagramsdiscuss@googlegroups.com 

Safe Haskell  None 
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) > (a > r > r) > DUALTreeNE d u a l > r
 foldDUAL :: (Semigroup d, Monoid d) => (d > l > r) > r > (NonEmpty 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 
Typeable4 DUALTreeNE  
(Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTreeNE d u a l)  
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  

Typeable4 DUALTreeU  
(Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTreeU d u a l)  
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  

Typeable4 DUALTree  
(Semigroup d, Semigroup u, Action d u) => Action (DAct d) (DUALTree d u a l)  Apply a 
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 lSource
The empty DUALtree. This is a synonym for mempty
, but with a
more general type.
leaf :: u > l > DUALTree d u a lSource
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 lSource
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 lSource
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 lSource
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 lSource
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 lSource
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 lSource
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 lSource
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 uSource
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 
> (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 
> (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, 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.
The result is Nothing
if and only if the tree is empty.