úÎSQ.     !diagrams-discuss@googlegroups.comNone'Rose (n-ary) trees with both upwards- (i.e. cached) and  downwards-traveling (i.e.% accumulating) monoidal annotations. D 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:  &, for modifying leaf data. Note that  of course  cannot alter any u annotations.  .  DUALTreeNEs form a semigroup where (<>) D corresponds to adjoining two trees under a common parent root,  with sconcat1 specialized to put all the trees under a single B parent. Note that this does not satisfy associativity up to C structural equality, but only up to observational equivalence  under . Technically using  directly enables > one to observe the difference, but it is understood that  5 should be used only in ways such that reassociation  of subtrees "does not matter".  ". The identity is the empty tree. +A non-empty DUAL-tree paired with a cached u value. These 6 should never be constructed directly; instead, use .  Non-empty DUAL-trees. Internal data value d annotation n-way branch, containing a  non-empty list  of subtrees. Leaf with only u annotation Leaf with data value and u annotation "Pull" the root u annotation out into a tuple. ,The empty DUAL-tree. This is a synonym for   , but with a  more general type. Construct a leaf node from a u annotation along with a leaf  datum. Construct a leaf node from a u annotation. Add a u9 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 =  u <> t. 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 <>  u. BAdd 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. Apply a d4 annotation at the root of a tree, transforming all  u annotations by the action of d. "Decompose a DUAL-tree into either Nothing (if empty) or a  top-level cached u$ annotation paired with a non-empty  DUAL-tree. Get the u annotation at the root, or Nothing if the tree is  empty. AMap 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. AMap 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. Map a function over all the u" annotations in a DUAL-tree. The E 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)Fold for non-empty DUAL-trees. AFold 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 2 constant value. In particular, however, it is not given access  to any of the u1 annotations, the idea being that those are used  only for  constructing" trees. If you do need access to u A 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 ! 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. AA specialized fold provided for convenience: flatten a tree into % a list of leaves along with their d annotations, ignoring  internal data values. "Apply a d6 annotation at the root of a tree. Semantically, all  u. annotations are transformed by the action of d , although  operationally act( incurs only a constant amount of work. '#$%  $Process a leaf datum along with the  accumulation of d values along the  path from the root Replace LeafU nodes !Combine results at a branch node Process an internal d node Process an internal datum $Process a leaf datum along with the  accumulation of d values along the  path from the root Replace u -only nodes !Combine results at a branch node Process an internal d node Process an internal datum "&'()*+,   #$%  "&'()*+,!diagrams-discuss@googlegroups.comNone  -      !"#$%#&#'())*+,-./012 dual-tree-0.2Data.Tree.DUAL.InternalData.Tree.DUALDUALTree unDUALTree DUALTreeU unDUALTreeU DUALTreeNEAnnotActConcatLeafULeafemptyleafleafU applyUpre applyUpostannotapplyDnonEmptygetUmapUNEmapUUmapU foldDUALNEfoldDUALflattenbaseGHC.BaseFunctorfmapsemigroups-0.11Data.Semigroup Semigroup Data.MonoidMonoidpullUmemptymconcat$fActionDActDUALTreeDActunDAct$fMonoidDUALTree$fNewtypeDUALTreeOption$fActionDActDUALTreeU$fNewtypeDUALTreeU(,)$fActionDActDUALTreeNE$fNewtypeDActd$fSemigroupDUALTreeNE