Rose (n-way) trees with both upwards- and downwards-traveling monoidal annotations, used as the basis for representing diagrams.
- data UDTree u d a
- leaf :: u -> a -> UDTree u d a
- branchD :: (Action d u, Monoid u) => d -> [UDTree u d a] -> UDTree u d a
- branch :: (Action d u, Monoid u, Monoid d) => [UDTree u d a] -> UDTree u d a
- applyD :: Action d u => d -> UDTree u d a -> UDTree u d a
- applyU :: (Monoid u, Action d u) => u -> UDTree u d a -> UDTree u d a
- mapU :: (u -> u') -> UDTree u d a -> UDTree u' d a
- getU :: Action d u => UDTree u d a -> u
- getU' :: (Action d (u' ::: Nil), u :>: u') => UDTree u d a -> u'
- foldUD :: (Monoid r, Monoid d, Action d u) => (u -> d -> a -> r) -> (u -> d -> r -> r) -> UDTree u d a -> r
- flatten :: (Monoid d, Action d u) => UDTree u d a -> [(a, d)]
Abstractly, a UDTree is a rose (n-way) tree with data at the
leaves and two types of monoidal annotations, one (called
travelling "up" the tree and one (called
Specifically, every node (both leaf nodes and internal nodes)
has two annotations, one of type
d and one of type
subject to the following constraints:
dannotation at a leaf node is equal to the
mconcatof all the
dannotations along the path from the root to the leaf node.
uannotation at an internal node is equal to
v `for some value
mappend` (mconcat us)
usis the list (in left-right order) of the
uannotations on the immediate child nodes of the given node. Intuitively, we are "caching" the
uannotations from the leaves up, except that at any point we may insert "extra" information.
d may have an action on
u (see the
type class, defined in Graphics.Rendering.Diagrams.Monoids), in
which case applying a
d annotation to a tree will transform all
u annotations by acting on them. The constraints on
annotations are maintained since the action is required to be a
|Functor (UDTree u d)|
|(Action d u, Monoid u, Monoid d) => Monoid (UDTree u d a)|
Construct a branch node with an explicit
Construct a branch node with a default (identity)
d annotation to the root, combining it (on the left) with
d annotation, and transforming all
annotations by the action of
u annotation to the root, combining it (on the left) with
Map a function over all the
u annotations. The function must
be a monoid homomorphism, and must commute with the action of
u. That is, to use
mapU f safely it must be the case that
f (act d u) == act d (f u).
Accessors and destructors
Get a particular component from a the
u annotation at the root.
This method is provided for convenience, since its context only
requires an action of
u', rather than on
u in its
|:: (Monoid r, Monoid d, Action d u)|
|=> (u -> d -> a -> r)|
Function for processing leaf nodes.
Given the u annotation at this node, the
|-> (u -> d -> r -> r)|
Function for processing internal
nodes. Given the u and d
annotations at this node and the
|-> UDTree u d a|
A fold for UDTrees.