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.
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
- 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
- setStem :: e -> Tree e a -> Tree e a
- applyStem :: (e -> e) -> Tree e a -> Tree e a
- branches :: Tree e a -> [e]
- setBranches :: Bitraversable t => [f] -> t e a -> Maybe (t f a)
- setLabel :: a -> Tree e a -> Tree e a
- applyLabel :: (a -> a) -> Tree e a -> Tree e a
- labels :: Tree e a -> [a]
- setLabels :: Traversable t => [b] -> t a -> Maybe (t b)
- applyRoot :: (a -> a) -> Tree e a -> Tree e a
- identify :: Traversable t => t a -> t Int
- degree :: Tree e a -> Int
- depth :: 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 (first
acts
on branches, second
on node labels).
Lifted instances are not provided.
Instances
Bifunctor Tree Source # | The function |
Bitraversable Tree Source # | |
Defined in ELynx.Tree.Rooted bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Tree a b -> f (Tree c d) # | |
Bifoldable Tree Source # | |
(Semigroup e, Monoid e) => Monad (Tree e) Source # | The The |
Functor (Tree e) Source # | Map over node labels. |
Monoid e => MonadFix (Tree e) Source # | |
Defined in ELynx.Tree.Rooted | |
(Semigroup e, Monoid e) => Applicative (Tree e) Source # | The The |
Foldable (Tree e) Source # | Combine node labels in pre-order. |
Defined in ELynx.Tree.Rooted fold :: 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 # 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.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 :: 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 # | |
(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.Tree.Rooted | |
(ToJSON e, ToJSON a) => ToJSON (Tree e a) Source # | |
Defined in ELynx.Tree.Rooted | |
(FromJSON e, FromJSON a) => FromJSON (Tree e a) Source # | |
type Rep (Tree e a) Source # | |
Defined in ELynx.Tree.Rooted type Rep (Tree e a) = D1 ('MetaData "Tree" "ELynx.Tree.Rooted" "elynx-tree-0.5.1.0-OnSTDMW2L1Ll7WyAwiVjK" '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.
applyLabel :: (a -> a) -> Tree e a -> Tree e a Source #
Change the root branch of a tree.
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.
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 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.