TQ.      !"#$%&'()*+,-(c) 2011-2012 Brent YorgeyBSD-style (see LICENSE)!diagrams-discuss@googlegroups.comNone 13;<=>?FKSTN'Rose (n-ary) trees with both upwards- (i.e.% cached) and downwards-traveling (i.e.l accumulating) monoidal annotations. Abstractly, a DUALTree is a rose (n-ary) tree with data (of type l) at leaves, data (of type aL) at internal nodes, and two types of monoidal annotations, one (of type u/) travelling "up" the tree and one (of type dW) 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.0.  DUALTreeNEs form a semigroup where (<>)O corresponds to adjoining two trees under a common parent root, with sconcat 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 under . Technically using U directly enables one to observe the difference, but it is understood that X should be used only in ways such that reassociation of subtrees "does not matter".1!. The identity is the empty tree.+A non-empty DUAL-tree paired with a cached uE value. These should never be constructed directly; instead, use 2. Non-empty DUAL-trees.Leaf with data value and u annotationLeaf with only u annotation n-way branch, containing a  non-empty list of subtrees. d annotation Internal data value2"Pull" the root u annotation out into a tuple. ,The empty DUAL-tree. This is a synonym for 3", 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 uP annotation to the root, combining it (on the left) with the existing cached uA annotation. This function is provided just for convenience; applyUpre u t =  u <> t.Add a uQ annotation to the root, combining it (on the right) with the existing cached uA annotation. This function is provided just for convenience; applyUpost u t = t <>  u.SAdd an internal data value at the root of a tree. Note that this only works on  non-empty8 trees; on empty trees this function is the identity.Apply a d7 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 u1 annotation paired with a non-empty DUAL-tree.Get the u annotation at the root, or Nothing if the tree is empty.WMap 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.WMap 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 ut annotations in a DUAL-tree. 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)Fold for non-empty DUAL-trees.SFold for DUAL-trees. It is given access to the internal and leaf data, internal d values, and the accumulated d9 values at each leaf. It is also allowed to replace "uG-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 uP 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 4 of all internal d4 values along the path from the root to the leaf.The result is Nothing" if and only if the tree is empty.fA specialized fold provided for convenience: flatten a tree into a list of leaves along with their d/ annotations, ignoring internal data values. Apply a d9 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.7Process a leaf datum along with the accumulation of d' values along the path from the rootReplace LeafU nodes Combine results at a branch nodeProcess an internal d nodeProcess an internal datum7Process a leaf datum along with the accumulation of d' values along the path from the rootReplace u -only nodes Combine results at a branch nodeProcess an internal d nodeProcess an internal datum    567 (c) 2011-2012 Brent YorgeyBSD-style (see LICENSE)!diagrams-discuss@googlegroups.comNoneQ*  8      !"#$%&'()*+,-./01/02/34/056/07/0899:;&dual-tree-0.2.2-7GavyX6PRDbBgHxPUgPHJrData.Tree.DUAL.InternalData.Tree.DUALDUALTree unDUALTree DUALTreeU unDUALTreeU DUALTreeNELeafLeafUConcatActAnnotemptyleafleafU applyUpre applyUpostannotapplyDnonEmptygetUmapUNEmapUUmapU foldDUALNEfoldDUALflatten $fNewtypeDAct$fActionDActDUALTreeU$fNewtypeDUALTreeU$fActionDActDUALTreeNE$fSemigroupDUALTreeNE$fActionDActDUALTree$fMonoidDUALTree$fNewtypeDUALTree$fFunctorDUALTreeU$fSemigroupDUALTreeU$fShowDUALTreeU $fEqDUALTreeU$fFunctorDUALTreeNE$fShowDUALTreeNE$fEqDUALTreeNE$fFunctorDUALTree$fSemigroupDUALTree$fShowDUALTree $fEqDUALTreebaseGHC.BaseFunctorfmapData.Semigroup SemigroupMonoidpullUmemptymconcatDActunDAct