Copyright | (c) Dominik Schrempf 2020 |
---|---|
License | GPL-3.0-or-later |
Maintainer | dominik.schrempf@gmail.com |
Stability | unstable |
Portability | portable |
Safe Haskell | None |
Language | Haskell2010 |
Creation date: Thu Jan 17 09:57:29 2019.
Rooted Tree
s differes from a classical rose Tree
in that it has
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 value constructor Node and the record function label are not to be
confused. The elements of the sub-forest are often called children.
With respect to phylogenetic analyses, using the Tree
data type has some
disadvantages:
- All trees are rooted. Unrooted trees can be treated with a rooted data structure, as it is used here. However, some functions may be meaningless.
- Changing branch labels, node labels, or the topology of the tree are slow operations, especially, when the changes are close to the leaves of the tree.
In mathematical terms: A Tree
is a directed acyclic graph without loops,
with vertex labels, with edge labels. Let me know if this definition is
incomplete.
Synopsis
- data Tree e a = Node {}
- type Forest e a = [Tree e a]
- toTreeBranchLabels :: Tree e a -> Tree e
- toTreeNodeLabels :: Tree e a -> Tree a
- leaves :: Tree e a -> [a]
- duplicateLeaves :: Ord a => Tree e a -> Bool
- branches :: Tree e a -> [e]
- setBranches :: Bitraversable t => [f] -> t e a -> Maybe (t f a)
- labels :: Tree e a -> [a]
- setLabels :: Traversable t => [b] -> t a -> Maybe (t b)
- identify :: Traversable t => t a -> t Int
- degree :: Tree e a -> Int
- prune :: Semigroup e => Tree e a -> Tree e a
- dropNodesWith :: (a -> Bool) -> Tree e a -> Maybe (Tree e a)
- dropLeavesWith :: (a -> Bool) -> Tree e a -> Maybe (Tree e a)
- zipTreesWith :: (e1 -> e2 -> e) -> (a1 -> a2 -> a) -> Tree e1 a1 -> Tree e2 a2 -> Maybe (Tree e a)
- zipTrees :: Tree e1 a1 -> Tree e2 a2 -> Maybe (Tree (e1, e2) (a1, a2))
Data type
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.
Lifted instances are not provided.
Instances
Bifunctor Tree Source # | |
Bitraversable Tree Source # | |
Defined in ELynx.Data.Tree.Rooted bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Tree a b -> f (Tree c d) # | |
Bifoldable Tree Source # | |
Monoid e => Monad (Tree e) Source # | The |
Functor (Tree e) Source # | Map over node labels. |
Monoid e => MonadFix (Tree e) Source # | |
Defined in ELynx.Data.Tree.Rooted | |
Monoid e => Applicative (Tree e) Source # | The The |
Foldable (Tree e) Source # | Combine node labels in pre-order. |
Defined in ELynx.Data.Tree.Rooted fold :: Monoid m => Tree e m -> 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 # elem :: Eq a => a -> Tree e a -> Bool # maximum :: Ord a => Tree e a -> a # minimum :: Ord a => Tree e a -> a # | |
Traversable (Tree e) Source # | |
Comonad (Tree e) Source # | |
(Eq e, Eq a) => Eq (Tree e a) Source # | |
(Data e, Data a) => Data (Tree e a) Source # | |
Defined in ELynx.Data.Tree.Rooted gfoldl :: (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 :: (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 # | |
(Show e, Show a) => Show (Tree e a) Source # | |
Generic (Tree e a) Source # | |
(NFData e, NFData a) => NFData (Tree e a) Source # | |
Defined in ELynx.Data.Tree.Rooted | |
(ToJSON e, ToJSON a) => ToJSON (Tree e a) Source # | |
Defined in ELynx.Data.Tree.Rooted | |
(FromJSON e, FromJSON a) => FromJSON (Tree e a) Source # | |
type Rep (Tree e a) Source # | |
Defined in ELynx.Data.Tree.Rooted type Rep (Tree e a) = D1 (MetaData "Tree" "ELynx.Data.Tree.Rooted" "elynx-tree-0.3.2-D4z8hEm7d0IGPFAaza2gb3" 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))))) |
Access leaves, branches and labels
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.
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 with unique integers starting at the root with 0.
Change structure
prune :: Semigroup e => Tree e a -> Tree e a Source #
Prune degree two nodes.
The information stored in 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 parent nodes of which all daughter nodes are dropped.
Return Nothing
if the root node satisfies the predicate.
dropLeavesWith :: (a -> Bool) -> Tree e a -> Maybe (Tree e a) Source #
Drop leaves satisfying predicate.
Degree two nodes may arise.
Also drop parent nodes of which all leaves are dropped.
Return Nothing
if all leaves satisfy the predicate.