Maintainer | diagrams-discuss@googlegroups.com |
---|---|
Safe Haskell | Safe-Infered |
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
- applyUpre :: (Semigroup u, Action d u) => u -> UDTree u d a -> UDTree u d a
- applyUpost :: (Semigroup 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, Semigroup d, Monoid d, Action d u) => (u -> d -> a -> r) -> (u -> d -> r -> r) -> UDTree u d a -> r
- flatten :: (Semigroup d, Monoid d, Action d u) => UDTree u d a -> [(a, d)]
UD-trees
Abstractly, a UDTree is a rose (n-way) tree with data at the
leaves and two types of monoidal annotations, one (called u
)
travelling "up" the tree and one (called d
) traveling
"down".
Specifically, every node (both leaf nodes and internal nodes)
has two annotations, one of type d
and one of type u
,
subject to the following constraints:
- The
d
annotation at a leaf node is equal to themconcat
of all thed
annotations along the path from the root to the leaf node. - The
u
annotation at an internal node is equal tov1 `
for some valuesmappend
` (mconcat us) `mappend
` v2v1
andv2
(possiblymempty
), whereus
is the list (in left-right order) of theu
annotations on the immediate child nodes of the given node. Intuitively, we are "caching" themconcat
ofu
annotations from the leaves up, except that at any point we may insert "extra" information.
In addition, d
may have an action on u
(see the Action
type class, defined in Graphics.Rendering.Diagrams.Monoids), in
which case applying a d
annotation to a tree will transform all
the u
annotations by acting on them. The constraints on u
annotations are maintained since the action is required to be a
monoid homomorphism.
Functor (UDTree u d) | |
(Action d u, Monoid u, Monoid d) => Monoid (UDTree u d a) |
|
(Action d u, Monoid u, Monoid d) => Semigroup (UDTree u d a) | |
Newtype (QDiagram b v m) (UDTree (UpAnnots v m) (DownAnnots v) (Prim b v)) |
Constructing UD-trees
branchD :: (Action d u, Monoid u) => d -> [UDTree u d a] -> UDTree u d aSource
Construct a branch node with an explicit d
annotation.
branch :: (Action d u, Monoid u, Monoid d) => [UDTree u d a] -> UDTree u d aSource
Construct a branch node with a default (identity) d
annotation.
Modifying UD-trees
applyD :: Action d u => d -> UDTree u d a -> UDTree u d aSource
Add a d
annotation to the root, combining it (on the left) with
any pre-existing d
annotation, and transforming all u
annotations by the action of d
.
applyUpre :: (Semigroup u, Action d u) => u -> UDTree u d a -> UDTree u d aSource
Add a u
annotation to the root, combining it (on the left) with
the existing u
annotation.
applyUpost :: (Semigroup u, Action d u) => u -> UDTree u d a -> UDTree u d aSource
Add a u
annotation to the root, combining it (on the right) with
the existing u
annotation.
mapU :: (u -> u') -> UDTree u d a -> UDTree u' d aSource
Map a function over all the u
annotations. 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 (act d u) == act d (f u)
.
Accessors and destructors
getU' :: (Action d (u' ::: Nil), u :>: u') => UDTree u d a -> u'Source
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 d
on u'
, rather than on u
in its
entirety.
:: (Monoid r, Semigroup d, 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 | |
-> r |
A fold for UDTrees.