Copyright | (c) Dominik Schrempf 2021 |
---|---|

License | GPL-3.0-or-later |

Maintainer | dominik.schrempf@gmail.com |

Stability | unstable |

Portability | portable |

Safe Haskell | None |

Language | Haskell2010 |

Creation date: Fri Aug 30 15:28:17 2019.

## Synopsis

- groups :: Tree e a -> Tree e [a]
- data Bipartition a
- bp :: Ord a => Set a -> Set a -> Either String (Bipartition a)
- bpUnsafe :: Ord a => Set a -> Set a -> Bipartition a
- toSet :: Ord a => Bipartition a -> Set a
- bpHuman :: Show a => Bipartition a -> String
- bipartition :: Ord a => Tree e a -> Either String (Bipartition a)
- bipartitions :: Ord a => Tree e a -> Either String (Set (Bipartition a))
- getComplementaryLeaves :: Ord a => Set a -> Tree e (Set a) -> [Set a]
- bipartitionToBranch :: (Semigroup e, Ord a) => Tree e a -> Either String (Map (Bipartition a) e)

# Documentation

groups :: Tree e a -> Tree e [a] Source #

Each node of a tree is root of an induced subtree. Set the node labels to the leaves of the induced subtrees.

# Data type

data Bipartition a Source #

A bipartition of a tree is a grouping of the leaves of the tree into two non-overlapping, non-empty sub sets.

For unrooted trees:

- Each branch partitions the leaves of the tree into two subsets, or a bipartition.

For rooted trees:

- A bifurcating root node induces a bipartition; see
`bipartition`

. - Each inner node induces a bipartition by taking the leaves of the sub tree and the complement leaf set of the full tree.

The order of the two subsets of a `Bipartition`

is meaningless. That is,
`Bipartition`

s are weird in that

Bipartition x y == Bipartition y x

is `True`

. Also,

Bipartition x y > Bipartition y x

is False, even when `x > y`

. That's why we have to make sure that for

Bipartition x y

we always have `x >= y`

. We ensure by construction that the larger subset
comes first, and so that equality checks are meaningful; see `bp`

and
`bpUnsafe`

.

#### Instances

bp :: Ord a => Set a -> Set a -> Either String (Bipartition a) Source #

Create a bipartition from two sets.

Ensure that the larger set comes first.

Return `Left`

if one set is empty.

bpUnsafe :: Ord a => Set a -> Set a -> Bipartition a Source #

Create a bipartition from two sets.

Ensure that the larger set comes first.

bpHuman :: Show a => Bipartition a -> String Source #

Show a bipartition in a human readable format. Use a provided function to extract information of interest.

# Work with `Bipartition`

s

bipartition :: Ord a => Tree e a -> Either String (Bipartition a) Source #

For a bifurcating root, get the bipartition induced by the root node.

Return `Left`

if
- the root node is not bifurcating;
- a leave set is empty.

bipartitions :: Ord a => Tree e a -> Either String (Set (Bipartition a)) Source #

Get all bipartitions of the tree.

Return `Left`

if the tree contains duplicate leaves.

getComplementaryLeaves :: Ord a => Set a -> Tree e (Set a) -> [Set a] Source #

Report the complementary leaves for each child.

bipartitionToBranch :: (Semigroup e, Ord a) => Tree e a -> Either String (Map (Bipartition a) e) Source #

Convert a tree into a `Map`

from each `Bipartition`

to the branch inducing
the respective `Bipartition`

.

Since the induced bipartitions of the daughter branches of a bifurcating root node are equal, the branches leading to the root have to be combined in this case. See http://evolution.genetics.washington.edu/phylip/doc/treedist.html and how unrooted trees are handled.

Further, branches connected to degree two nodes also induce the same bipartitions and have to be combined.

For combining branches, a binary function is required. This requirement is
encoded in the `Semigroup`

type class constraint (see `prune`

).

Return `Left`

if the tree contains duplicate leaves.