dual-tree-0.2.3.1: Rose trees with cached and accumulating monoidal annotations

Copyright | (c) 2011-2012 Brent Yorgey
License | BSD-style (see LICENSE)
Maintainer | diagrams-discuss@googlegroups.com
Safe Haskell | None
Language | Haskell2010

Data.Tree.DUAL

Contents

- DUAL-trees
- Constructing DUAL-trees
- Modifying DUAL-trees
- Accessors and eliminators

Description

Rose (n-ary) trees with both upwards- (i.e. cached) and downwards-traveling (i.e. accumulating) monoidal annotations. This is used as the core data structure underlying the `diagrams` framework (https://diagrams.github.io), but potentially has other applications as well.

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".

Specifically, there are five types of nodes:

- Leaf nodes which contain a data value of type `l` and an annotation of type `u`. The annotation represents information about a tree that should be accumulated (e.g. number of leaves, some sort of "weight", etc.). If you are familiar with finger trees (http://www.soi.city.ac.uk/~ross/papers/FingerTree.html, http://hackage.haskell.org/package/fingertree), it is the same idea.
- There is also a special type of leaf node which contains only a `u` value, and no data. This allows cached `u` values to be "modified" by inserting extra annotations.
- Branch nodes, containing a list of subtrees.
- Internal nodes with a value of type `d`. `d` may have an action on `u` (see the `Action` type class, defined in Data.Monoid.Action from the `monoid-extras` package). Semantically speaking, applying a `d` annotation to a tree transforms all the `u` annotations below it by acting on them. Operationally, however, since the action must be a monoid homomorphism, applying a `d` annotation can actually be done in constant time.
- Internal nodes with data values of type `a`, possibly of a different type than those in the leaves. These are just "along for the ride" and are unaffected by `u` and `d` annotations.

There are two critical points to note about `u` and `d` annotations:

- The combined `u` annotation for an entire tree is always cached at the root and available in constant (amortized) time.
- The `mconcat` of all the `d` annotations along the path from the root to each leaf is available along with the leaf during a fold operation.

A fold over a `DUALTree` 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.

Synopsis

- data DUALTree 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
- mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l
- getU :: DUALTree d u a l -> Maybe u
- foldDUAL :: (Semigroup d, Monoid d) => (d -> l -> r) -> r -> (NonEmpty r -> r) -> (d -> r -> r) -> (a -> r -> r) -> DUALTree d u a l -> Maybe r
- flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)]

# DUAL-trees

data DUALTree d u a l Source #

Rose (n-ary) trees with both upwards- (i.e. cached) and downwards-traveling (i.e. accumulating) monoidal annotations. 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:

- `Functor`, for modifying leaf data. Note that `fmap` of course cannot alter any `u` annotations.
- `Semigroup`. `DUALTreeNE`s form a semigroup where `(<>)` 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 `flatten`. Technically using `foldDUAL` directly enables one to observe the difference, but it is understood that `foldDUAL` should be used only in ways such that reassociation of subtrees "does not matter".
- `Monoid`. The identity is the empty tree.

#### Instances

Instances details

Functor (DUALTree d u a) Source # |
Instance details Defined in Data.Tree.DUAL.Internal Methods fmap :: (a0 -> b) -> DUALTree d u a a0 -> DUALTree d u a b Source # (<$) :: a0 -> DUALTree d u a b -> DUALTree d u a a0 Source #
(Semigroup u, Action d u) => Monoid (DUALTree d u a l) Source # |
Instance details Defined in Data.Tree.DUAL.Internal Methods mempty :: DUALTree d u a l Source # mappend :: DUALTree d u a l -> DUALTree d u a l -> DUALTree d u a l Source # mconcat :: [DUALTree d u a l] -> DUALTree d u a l Source #
(Semigroup u, Action d u) => Semigroup (DUALTree d u a l) Source # |
Instance details Defined in Data.Tree.DUAL.Internal Methods (<>) :: DUALTree d u a l -> DUALTree d u a l -> DUALTree d u a l Source # sconcat :: NonEmpty (DUALTree d u a l) -> DUALTree d u a l Source # stimes :: Integral b => b -> DUALTree d u a l -> DUALTree d u a l Source #
(Show u, Show l, Show d, Show a) => Show (DUALTree d u a l) Source # |
Instance details Defined in Data.Tree.DUAL.Internal Methods showsPrec :: Int -> DUALTree d u a l -> ShowS Source # show :: DUALTree d u a l -> String Source # showList :: [DUALTree d u a l] -> ShowS Source #
(Eq u, Eq l, Eq d, Eq a) => Eq (DUALTree d u a l) Source # |
Instance details Defined in Data.Tree.DUAL.Internal Methods (==) :: DUALTree d u a l -> DUALTree d u a l -> Bool Source # (/=) :: DUALTree d u a l -> DUALTree d u a l -> Bool Source #

# Constructing DUAL-trees

empty :: DUALTree d u a l Source #

The empty DUAL-tree. This is a synonym for `mempty`, but with a more general type.

leaf :: u -> l -> DUALTree d u a l Source #

Construct a leaf node from a `u` annotation along with a leaf datum.

leafU :: u -> DUALTree d u a l Source #

Construct a leaf node from a `u` annotation.

annot :: (Semigroup u, Action d u) => a -> DUALTree d u a l -> DUALTree d u a l Source #

Add 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.

applyD :: (Semigroup d, Semigroup u, Action d u) => d -> DUALTree d u a l -> DUALTree d u a l Source #

Apply a `d` annotation at the root of a tree, transforming all `u` annotations by the action of `d`.

# Modifying DUAL-trees

applyUpre :: (Semigroup u, Action d u) => u -> DUALTree d u a l -> DUALTree d u a l Source #

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 l Source #

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`.

mapU :: (u -> u') -> DUALTree d u a l -> DUALTree d u' a l Source #

Map a function over all the `u` 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)

# Accessors and eliminators

getU :: DUALTree d u a l -> Maybe u Source #

Get the `u` annotation at the root, or `Nothing` if the tree is empty.

foldDUAL Source #

Arguments

:: (Semigroup d, Monoid d) |
=> (d -> l -> r) | Process a leaf datum along with the accumulation of `d` values along the path from the root
-> r | Replace `u`-only nodes
-> (NonEmpty r -> r) | Combine results at a branch node
-> (d -> r -> r) | Process an internal d node
-> (a -> r -> r) | Process an internal datum
-> DUALTree d u a l |
-> Maybe r |

Fold 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 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 `u` 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 `mconcat` 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.

flatten :: (Semigroup d, Monoid d) => DUALTree d u a l -> [(l, d)] Source #

A specialized fold provided for convenience: flatten a tree into a list of leaves along with their `d` annotations, ignoring internal data values.