Data.Named.Tree

Working with NE trees and forests.

Auxiliary types

type NeTree a b = Tree (Either a b)

A tree with a values in internal nodes and b values in leaves.

type NeForest a b = Forest (Either a b)

A forest with a values in internal nodes and b values in leaves.

Span

data Span w

Spanning of a tree.

Constructors

Span

Fields

• beg :: w
• end :: w

Instances

Eq w => Eq (Span w)

Defined in Data.Named.Tree

Methods

(==) :: Span w -> Span w -> Bool

(/=) :: Span w -> Span w -> Bool

Ord w => Ord (Span w)

Defined in Data.Named.Tree

Methods

compare :: Span w -> Span w -> Ordering

(<) :: Span w -> Span w -> Bool

(<=) :: Span w -> Span w -> Bool

(>) :: Span w -> Span w -> Bool

(>=) :: Span w -> Span w -> Bool

max :: Span w -> Span w -> Span w

min :: Span w -> Span w -> Span w

Show w => Show (Span w)

Defined in Data.Named.Tree

Methods

showsPrec :: Int -> Span w -> ShowS

show :: Span w -> String

showList :: [Span w] -> ShowS

leafSpan :: w -> Span w

Make span for a leaf node.

(<>) :: Ord w => Span w -> Span w -> Span w

Minimum span overlapping both input spans.

spanSet :: Ix w => Span w -> Set w

Set of positions covered by the span.

Trees with span

span :: Tree (a, Span w) -> Span w

Get span of the span-annotated tree.

spanTree :: Ord w => Tree (Either n w) -> Tree (Either n w, Span w)

Annotate tree nodes with spanning info given the function which assignes indices to leaf nodes.

spanForest :: Ord w => Forest (Either n w) -> Forest (Either n w, Span w)

Annotate forest nodes with spanning info.

unSpanTree :: Tree (k, Span w) -> Tree k

Remove span annotations from the tree.

unSpanForest :: Forest (k, Span w) -> Forest k

Remove span annotations from the forest.

sortTree :: Ord w => Tree (k, Span w) -> Tree (k, Span w)

Sort the tree with respect to spanning info.

sortForest :: Ord w => Forest (k, Span w) -> Forest (k, Span w)

Sort the forest with respect to spanning info.

Utilities

mapForest :: (a -> b) -> Forest a -> Forest b

Map function over each tree from the forest.

mapTree :: (a -> b) -> Tree a -> Tree b

Map function over the tree.

onLeaf :: (a -> b) -> Either c a -> Either c b

Map function over the leaf value.

onNode :: (a -> b) -> Either a c -> Either b c

Map function over the internal node value.

onEither :: (a -> c) -> (b -> d) -> Either a b -> Either c d

Map the first function over internal node value and the second one over leaf value.

onBoth :: (a -> b) -> Either a a -> Either b b

Map one function over both node and leaf values.

groupForestLeaves :: (b -> b -> Bool) -> NeForest a b -> NeForest a [b]

Group leaves with respect to the given equality function.

groupTreeLeaves :: (b -> b -> Bool) -> NeTree a b -> NeTree a [b]

Group leaves with respect to the given equality function.

concatForestLeaves :: NeForest a [b] -> NeForest a b

Group leaves with respect to the given equality function.

concatTreeLeaves :: NeTree a [b] -> NeForest a b

Group leaves with respect to the given equality function.

module Data.Tree