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 or remove 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.

partitionTree :: Ord a => Tree a -> Tree (Subset a)

Each node of a tree is root of a subtree. Get the leaves of the subtree of each node.

subForestGetSubsets

Arguments

:: Ord a

=> Subset a

Complementary partition at the stem

-> Tree (Subset a)

Tree with partition nodes

-> [Subset a]

Loop through each tree in a forest to report the complementary leaf sets.

bifurcating :: Tree a -> Bool

Check if a tree is bifurcating and does not include degree two nodes. I know, one should use a proper data structure to encode bifurcating trees, but I don't have enough time for this now.

roots :: Tree a -> [Tree a]

For a rooted, bifurcating tree, get all possible rooted trees. For a tree with n>2 leaves, there are (2n-3) rooted trees. Beware, a bifurcating tree without degree two nodes is assumed (see bifurcating). The root node is moved.

connect :: a -> Tree a -> Tree a -> [Tree a]

Connect two trees in all possible ways.

Basically, introduce a branch between two trees. If the trees have n, and m branches, respectively, there are n*m ways to connect them.

A base node has to be given which will be used wherever the new node is introduced.

clades :: Ord a => Tree a -> [Subset a]

Get clades induced by multifurcations.

XXX: Probably introduce a new module defining a Clade.