ELynx.Data.Tree.Tree

Creation date: Thu Jan 17 09:57:29 2019.

Comment about nomenclature:

• In Data.Tree, a Tree is defined as

data Tree a = Node {
        rootLabel :: a,         -- ^ label value
        subForest :: Forest a   -- ^ zero or more child trees
    }

This means, that the word Node is reserved for the constructor of a tree, and that a Node has a label and a children. The terms Node and label are not to be confused.

• Branches have lengths. For example, a branch length can be a distances or a time.

NOTE: Trees in this library are all rooted. Unrooted trees can be treated with a rooted data structure equally well. However, in these cases, some functions have no meaning. For example, functions measuring the distance from the root to the leaves (the height of a rooted tree).

NOTE: Try fgl or alga. Use functional graph library for unrooted trees see also the book Haskell high performance programming from Thomasson, p. 344.

Documentation

singleton :: a -> Tree a

The simplest tree. Usually an extant leaf.

degree :: Tree a -> Int

The degree of the root node of a tree.

leaves :: Tree a -> [a]

Get leaves of tree.

subTree :: (a -> Bool) -> Tree a -> Maybe (Tree a)

Get subtree of Tree with nodes satisfying predicate. Return Nothing, if no leaf satisfies predicate. At the moment: recursively, for each child, take the child if any leaf in the child satisfies the predicate.

subSample :: (PrimMonad m, Ord a) => Seq a -> Int -> Tree a -> Gen (PrimState m) -> m (Maybe (Tree a))

Extract a random sub tree with N leaves of a tree with M leaves, where M>N (otherwise error). The complete list of leaves (names are assumed to be unique) has to be provided as a Seq, and a Set, so that we have fast sub-sampling as well as lookup and don't have to recompute them when many sub-samples are requested.

nSubSamples :: (PrimMonad m, Ord a) => Int -> Seq a -> Int -> Tree a -> Gen (PrimState m) -> m [Maybe (Tree a)]

See subSample, but n times.

pruneWith :: (a -> a -> a) -> Tree a -> Tree a

Prune degree 2 inner nodes. The information stored in a pruned node can be used to change the daughter node. To discard this information, use, pruneWith const tree, otherwise pruneWith (daughter parent -> combined) tree.

merge :: Tree a -> Tree b -> Maybe (Tree (a, b))

Merge two trees with the same topology. Returns Nothing if the topologies are different.

tZipWith :: Traversable t => (a -> b -> c) -> [a] -> t b -> Maybe (t c)

Apply a function with different effect on each node to a Traversable. Based on https://stackoverflow.com/a/41523456.