elynx-tree-0.6.0.0: Handle phylogenetic trees

ELynx.Tree.Rooted

Description

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

Rooted Trees differs from a classical rose Trees in that they have labeled branches.

For rooted topologies, please see Rooted.

A Tree is defined as:

data Tree e a = Node
{ branch :: e,
label :: a,
forest :: Forest e a
}


where

type Forest e a = [Tree e a]


This means, that the word Node is reserved for the constructor of a tree, and that a Node has an attached branch, a label, and a sub-forest. The terms Node and label referring to the value constructor Node and the record function label, respectively, are not to be confused. The elements of the sub-forest are often called children.

In mathematical terms: A Tree is a directed acyclic graph without loops, with vertex labels, and with edge labels.

A short recap of recursive tree traversals:

• Pre-order: Root first, then sub trees from left to right. Also called depth first.
• In-order: Only valid for bifurcating trees. Left sub tree first, then root, then right sub tree.
• Post-order: Sub trees from left to right, then the root. Also called breadth first.

Here, pre-order traversals are used exclusively, for example, by accessor functions such as branches, or labels which is the same as toList. Please let me know, if post-order algorithms are required.

Synopsis

# Tree with branch labels

data Tree e a Source #

Rooted rose trees with branch labels.

Unary instances such as Functor act on node labels, and not on branch labels. Binary instances such as Bifunctor act on both labels (first acts on branches, second on node labels).

Constructors

 Node Fieldsbranch :: e label :: a forest :: Forest e a

#### Instances

Instances details
 Source # The function first acts on branch labels, second on node labels. Instance detailsDefined in ELynx.Tree.Rooted Methodsbimap :: (a -> b) -> (c -> d) -> Tree a c -> Tree b d #first :: (a -> b) -> Tree a c -> Tree b c #second :: (b -> c) -> Tree a b -> Tree a c # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsbitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Tree a b -> f (Tree c d) # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsbifold :: Monoid m => Tree m m -> m #bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> Tree a b -> m #bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Tree a b -> c #bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Tree a b -> c # (Semigroup e, Monoid e) => Monad (Tree e) Source # The Semigroup instance of the branch labels determines how the branches are combined. For example, distances can be summed using Sum.The Monoid instance of the branch labels determines the default branch label when using return. Instance detailsDefined in ELynx.Tree.Rooted Methods(>>=) :: Tree e a -> (a -> Tree e b) -> Tree e b #(>>) :: Tree e a -> Tree e b -> Tree e b #return :: a -> Tree e a # Functor (Tree e) Source # Map over node labels. Instance detailsDefined in ELynx.Tree.Rooted Methodsfmap :: (a -> b) -> Tree e a -> Tree e b #(<$) :: a -> Tree e b -> Tree e a # (Semigroup e, Monoid e) => Applicative (Tree e) Source # The Semigroup instance of the branch labels determines how the branches are combined. For example, distances can be summed using Sum.The Monoid instance of the branch labels determines the default branch label when using pure.This instance is similar to the one provided by Tree. For an alternative, see ZipTree. Instance detailsDefined in ELynx.Tree.Rooted Methodspure :: a -> Tree e a #(<*>) :: Tree e (a -> b) -> Tree e a -> Tree e b #liftA2 :: (a -> b -> c) -> Tree e a -> Tree e b -> Tree e c #(*>) :: Tree e a -> Tree e b -> Tree e b #(<*) :: Tree e a -> Tree e b -> Tree e a # Foldable (Tree e) Source # Combine node labels in pre-order. Instance detailsDefined in ELynx.Tree.Rooted Methodsfold :: Monoid m => Tree e m -> m #foldMap :: Monoid m => (a -> m) -> Tree e a -> m #foldMap' :: Monoid m => (a -> m) -> Tree e a -> m #foldr :: (a -> b -> b) -> b -> Tree e a -> b #foldr' :: (a -> b -> b) -> b -> Tree e a -> b #foldl :: (b -> a -> b) -> b -> Tree e a -> b #foldl' :: (b -> a -> b) -> b -> Tree e a -> b #foldr1 :: (a -> a -> a) -> Tree e a -> a #foldl1 :: (a -> a -> a) -> Tree e a -> a #toList :: Tree e a -> [a] #null :: Tree e a -> Bool #length :: Tree e a -> Int #elem :: Eq a => a -> Tree e a -> Bool #maximum :: Ord a => Tree e a -> a #minimum :: Ord a => Tree e a -> a #sum :: Num a => Tree e a -> a #product :: Num a => Tree e a -> a # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodstraverse :: Applicative f => (a -> f b) -> Tree e a -> f (Tree e b) #sequenceA :: Applicative f => Tree e (f a) -> f (Tree e a) #mapM :: Monad m => (a -> m b) -> Tree e a -> m (Tree e b) #sequence :: Monad m => Tree e (m a) -> m (Tree e a) # Comonad (Tree e) Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsextract :: Tree e a -> a #duplicate :: Tree e a -> Tree e (Tree e a) #extend :: (Tree e a -> b) -> Tree e a -> Tree e b # (Eq e, Eq a) => Eq (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Methods(==) :: Tree e a -> Tree e a -> Bool #(/=) :: Tree e a -> Tree e a -> Bool # (Data e, Data a) => Data (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsgfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tree e a -> c (Tree e a) #gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tree e a) #toConstr :: Tree e a -> Constr #dataTypeOf :: Tree e a -> DataType #dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tree e a)) #dataCast2 :: Typeable t => (forall d e0. (Data d, Data e0) => c (t d e0)) -> Maybe (c (Tree e a)) #gmapT :: (forall b. Data b => b -> b) -> Tree e a -> Tree e a #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree e a -> r #gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree e a -> r #gmapQ :: (forall d. Data d => d -> u) -> Tree e a -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> Tree e a -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tree e a -> m (Tree e a) #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree e a -> m (Tree e a) #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree e a -> m (Tree e a) # (Read e, Read a) => Read (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodsreadsPrec :: Int -> ReadS (Tree e a) #readList :: ReadS [Tree e a] #readPrec :: ReadPrec (Tree e a) #readListPrec :: ReadPrec [Tree e a] # (Show e, Show a) => Show (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodsshowsPrec :: Int -> Tree e a -> ShowS #show :: Tree e a -> String #showList :: [Tree e a] -> ShowS # Generic (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Associated Typestype Rep (Tree e a) :: Type -> Type # Methodsfrom :: Tree e a -> Rep (Tree e a) x #to :: Rep (Tree e a) x -> Tree e a # (NFData e, NFData a) => NFData (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsrnf :: Tree e a -> () # (ToJSON e, ToJSON a) => ToJSON (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodstoJSON :: Tree e a -> Value #toEncoding :: Tree e a -> Encoding #toJSONList :: [Tree e a] -> Value #toEncodingList :: [Tree e a] -> Encoding # (FromJSON e, FromJSON a) => FromJSON (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodsparseJSON :: Value -> Parser (Tree e a) #parseJSONList :: Value -> Parser [Tree e a] # type Rep (Tree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted type Rep (Tree e a) = D1 ('MetaData "Tree" "ELynx.Tree.Rooted" "elynx-tree-0.6.0.0-FQkEU9t6m33732ommPyIXg" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "branch") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 e) :*: (S1 ('MetaSel ('Just "label") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "forest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Forest e a))))) type Forest e a = [Tree e a] Source # Shorthand. fromRoseTree :: Tree a -> Tree () a Source # Conversion from Tree. toTreeBranchLabels :: Tree e a -> Tree e Source # Conversion to Tree using branch labels. toTreeNodeLabels :: Tree e a -> Tree a Source # Conversion to Tree using node labels. # Access leaves, branches and labels leaves :: Tree e a -> [a] Source # List of leaves. duplicateLeaves :: Ord a => Tree e a -> Bool Source # Check if a tree has duplicate leaves. setStem :: e -> Tree e a -> Tree e a Source # Set the stem to a given value. modifyStem :: (e -> e) -> Tree e a -> Tree e a Source # Modify the stem of a tree. branches :: Tree e a -> [e] Source # Get branch labels in pre-order. setBranches :: Bitraversable t => [f] -> t e a -> Maybe (t f a) Source # Set branch labels in pre-order. Return Nothing if the provided list of branch labels is too short. setLabel :: a -> Tree e a -> Tree e a Source # Set label. modifyLabel :: (a -> a) -> Tree e a -> Tree e a Source # Modify the root label of a tree. labels :: Tree e a -> [a] Source # Return node labels in pre-order. setLabels :: Traversable t => [b] -> t a -> Maybe (t b) Source # Set node labels in pre-order. Return Nothing if the provided list of node labels is too short. identify :: Traversable t => t a -> t Int Source # Label the nodes in pre-order with unique indices starting at 0. # Structure degree :: Tree e a -> Int Source # Degree of the root node. The degree of a node is the number of branches attached to the node. depth :: Tree e a -> Int Source # Depth of a tree. The depth of a tree is the largest number of nodes traversed on a path from the root to a leaf. By convention, the depth is larger equal 1. That is, the depth of a leaf tree is 1. prune :: Semigroup e => Tree e a -> Tree e a Source # Prune degree two nodes. The label of a pruned node is lost. The branches are combined according to their Semigroup instance of the form daughterBranch parentBranch -> combinedBranch. dropNodesWith :: (a -> Bool) -> Tree e a -> Maybe (Tree e a) Source # Drop nodes satisfying predicate. Degree two nodes may arise. Also drop nodes of which all daughter nodes are dropped. Return Nothing if • The root node satisfies the predicate. • All daughter nodes of the root are dropped. dropLeavesWith :: (a -> Bool) -> Tree e a -> Maybe (Tree e a) Source # Drop leaves satisfying predicate. Degree two nodes may arise. Also drop nodes of which all daughter nodes are dropped. Return Nothing if all leaves satisfy the predicate. zipTreesWith :: (e1 -> e2 -> e) -> (a1 -> a2 -> a) -> Tree e1 a1 -> Tree e2 a2 -> Maybe (Tree e a) Source # Zip two trees with the same topology. This function differs from the Applicative instance of ZipTree in that it fails when the topologies don't match. Further, it allows specification of a zipping function for the branches. Return Nothing if the topologies are different. zipTrees :: Tree e1 a1 -> Tree e2 a2 -> Maybe (Tree (e1, e2) (a1, a2)) Source # See zipTreesWith. flipLabels :: Tree e a -> Tree a e Source # Flip the branch and node lables. # Newtypes with specific instances newtype ZipTree e a Source # This newtype provides a zip-like applicative instance, similar to ZipList. The default applicative instance of Tree is not zip-like, because the zip-like instance makes the Monad instance meaningless (similar to the behavior observed with lists). Constructors  ZipTree FieldsgetZipTree :: Tree e a #### Instances Instances details  Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsfmap :: (a -> b) -> ZipTree e a -> ZipTree e b #(<$) :: a -> ZipTree e b -> ZipTree e a # Monoid e => Applicative (ZipTree e) Source # The Monoid instance of the branch labels determines the default branch label, and how the branches are combined. For example, distances can be summed using the Sum monoid.>>> let t = ZipTree $Node "" 0 [Node "" 1 [], Node "" 2 []] :: ZipTree String Int >>> let f = ZipTree$ Node "+3" (+3) [Node "*5" (*5) [], Node "+10" (+10) []] :: ZipTree String (Int -> Int) >>> f <*> t ZipTree {getZipTree = Node {branch = "+3", label = 3, forest = [Node {branch = "*5", label = 5, forest = []},Node {branch = "+10", label = 12, forest = []}]}} Instance detailsDefined in ELynx.Tree.Rooted Methodspure :: a -> ZipTree e a #(<*>) :: ZipTree e (a -> b) -> ZipTree e a -> ZipTree e b #liftA2 :: (a -> b -> c) -> ZipTree e a -> ZipTree e b -> ZipTree e c #(*>) :: ZipTree e a -> ZipTree e b -> ZipTree e b #(<*) :: ZipTree e a -> ZipTree e b -> ZipTree e a # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsfold :: Monoid m => ZipTree e m -> m #foldMap :: Monoid m => (a -> m) -> ZipTree e a -> m #foldMap' :: Monoid m => (a -> m) -> ZipTree e a -> m #foldr :: (a -> b -> b) -> b -> ZipTree e a -> b #foldr' :: (a -> b -> b) -> b -> ZipTree e a -> b #foldl :: (b -> a -> b) -> b -> ZipTree e a -> b #foldl' :: (b -> a -> b) -> b -> ZipTree e a -> b #foldr1 :: (a -> a -> a) -> ZipTree e a -> a #foldl1 :: (a -> a -> a) -> ZipTree e a -> a #toList :: ZipTree e a -> [a] #null :: ZipTree e a -> Bool #length :: ZipTree e a -> Int #elem :: Eq a => a -> ZipTree e a -> Bool #maximum :: Ord a => ZipTree e a -> a #minimum :: Ord a => ZipTree e a -> a #sum :: Num a => ZipTree e a -> a #product :: Num a => ZipTree e a -> a # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodstraverse :: Applicative f => (a -> f b) -> ZipTree e a -> f (ZipTree e b) #sequenceA :: Applicative f => ZipTree e (f a) -> f (ZipTree e a) #mapM :: Monad m => (a -> m b) -> ZipTree e a -> m (ZipTree e b) #sequence :: Monad m => ZipTree e (m a) -> m (ZipTree e a) # Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsextract :: ZipTree e a -> a #duplicate :: ZipTree e a -> ZipTree e (ZipTree e a) #extend :: (ZipTree e a -> b) -> ZipTree e a -> ZipTree e b # (Eq e, Eq a) => Eq (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Methods(==) :: ZipTree e a -> ZipTree e a -> Bool #(/=) :: ZipTree e a -> ZipTree e a -> Bool # (Data e, Data a) => Data (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Methodsgfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> ZipTree e a -> c (ZipTree e a) #gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (ZipTree e a) #toConstr :: ZipTree e a -> Constr #dataTypeOf :: ZipTree e a -> DataType #dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (ZipTree e a)) #dataCast2 :: Typeable t => (forall d e0. (Data d, Data e0) => c (t d e0)) -> Maybe (c (ZipTree e a)) #gmapT :: (forall b. Data b => b -> b) -> ZipTree e a -> ZipTree e a #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> ZipTree e a -> r #gmapQr :: forall r r'. (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> ZipTree e a -> r #gmapQ :: (forall d. Data d => d -> u) -> ZipTree e a -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> ZipTree e a -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> ZipTree e a -> m (ZipTree e a) #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> ZipTree e a -> m (ZipTree e a) #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> ZipTree e a -> m (ZipTree e a) # (Read e, Read a) => Read (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodsreadsPrec :: Int -> ReadS (ZipTree e a) #readList :: ReadS [ZipTree e a] #readPrec :: ReadPrec (ZipTree e a) #readListPrec :: ReadPrec [ZipTree e a] # (Show e, Show a) => Show (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted MethodsshowsPrec :: Int -> ZipTree e a -> ShowS #show :: ZipTree e a -> String #showList :: [ZipTree e a] -> ShowS # Generic (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted Associated Typestype Rep (ZipTree e a) :: Type -> Type # Methodsfrom :: ZipTree e a -> Rep (ZipTree e a) x #to :: Rep (ZipTree e a) x -> ZipTree e a # type Rep (ZipTree e a) Source # Instance detailsDefined in ELynx.Tree.Rooted type Rep (ZipTree e a) = D1 ('MetaData "ZipTree" "ELynx.Tree.Rooted" "elynx-tree-0.6.0.0-FQkEU9t6m33732ommPyIXg" 'True) (C1 ('MetaCons "ZipTree" 'PrefixI 'True) (S1 ('MetaSel ('Just "getZipTree") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree e a))))

newtype BranchTree a e Source #

This newtype provides instances acting on the branch labels, and not on the node labels as it is the case in Tree.

Constructors

 BranchTree FieldsgetBranchTree :: Tree e a

#### Instances

Instances details