License	GNU LGPLv3
Maintainer	paul.bittner@uni-ulm.de
Safe Haskell	Safe

Tree

Description

Implementation of a rose tree (i.e., a tree whose nodes can have an arbitrary amount of children, including 0) we use for ASTs .

Synopsis

data Tree a = Tree a [Tree a]
isleaf :: Tree a -> Bool
element :: Tree a -> a
tree :: (Eq a, Show a) => Tree a -> a -> Tree a
safetree :: Eq a => Tree a -> a -> Maybe (Tree a)
toset :: Ord a => Tree a -> Set a
find :: (Tree a -> Bool) -> Tree a -> Maybe (Tree a)
findByNode :: (a -> Bool) -> Tree a -> Maybe (Tree a)
parent :: Eq a => Tree a -> Tree a -> Maybe (Tree a)
ancestors :: Eq a => Tree a -> Tree a -> [Tree a]
manipulate :: (Tree a -> Tree a) -> Tree a -> Tree a
filterTrees :: (Tree a -> Bool) -> Tree a -> Tree a
filterNodes :: (Tree a -> Bool) -> Tree a -> Tree a
prettyPrint :: (Show a, Monoid b) => Int -> (String -> b) -> (a -> b) -> Tree a -> b

Documentation

data Tree a Source #

Rose tree of elements of type a where children of nodes are given as lists.

Constructors

Tree a [Tree a]

Instances

Instances details

Functor Tree Source #
Instance details Defined in Tree Methods fmap :: (a -> b) -> Tree a -> Tree b (<$) :: a -> Tree b -> Tree a
Applicative Tree Source #
Instance details Defined in Tree Methods pure :: a -> Tree a (<>) :: Tree (a -> b) -> Tree a -> Tree b liftA2 :: (a -> b -> c) -> Tree a -> Tree b -> Tree c (>) :: Tree a -> Tree b -> Tree b (<*) :: Tree a -> Tree b -> Tree a
Foldable Tree Source #
Instance details Defined in Tree Methods fold :: Monoid m => Tree m -> m foldMap :: Monoid m => (a -> m) -> Tree a -> m foldMap' :: Monoid m => (a -> m) -> Tree a -> m foldr :: (a -> b -> b) -> b -> Tree a -> b foldr' :: (a -> b -> b) -> b -> Tree a -> b foldl :: (b -> a -> b) -> b -> Tree a -> b foldl' :: (b -> a -> b) -> b -> Tree a -> b foldr1 :: (a -> a -> a) -> Tree a -> a foldl1 :: (a -> a -> a) -> Tree a -> a toList :: Tree a -> [a] null :: Tree a -> Bool length :: Tree a -> Int elem :: Eq a => a -> Tree a -> Bool maximum :: Ord a => Tree a -> a minimum :: Ord a => Tree a -> a sum :: Num a => Tree a -> a product :: Num a => Tree a -> a
Traversable Tree Source #
Instance details Defined in Tree Methods traverse :: Applicative f => (a -> f b) -> Tree a -> f (Tree b) sequenceA :: Applicative f => Tree (f a) -> f (Tree a) mapM :: Monad m => (a -> m b) -> Tree a -> m (Tree b) sequence :: Monad m => Tree (m a) -> m (Tree a)
Eq a => Eq (Tree a) Source #
Instance details Defined in Tree Methods (==) :: Tree a -> Tree a -> Bool (/=) :: Tree a -> Tree a -> Bool
Show a => Show (Tree a) Source #
Instance details Defined in Tree Methods showsPrec :: Int -> Tree a -> ShowS show :: Tree a -> String showList :: [Tree a] -> ShowS

isleaf :: Tree a -> Bool Source #

Returns true iff the given tree is a leaf (i.e., it has no children).

element :: Tree a -> a Source #

Returns the value stored in the root of the given tree.

tree :: (Eq a, Show a) => Tree a -> a -> Tree a Source #

Finds a subtree in the given tree (first argument) whose root has the given value (second argument). Throws an error iff no such tree exists.

safetree :: Eq a => Tree a -> a -> Maybe (Tree a) Source #

Same as tree but returns Nothing in the error case (i.e., when no subtree contains the given value).

toset :: Ord a => Tree a -> Set a Source #

Transforms a tree into a set. The returned set contains exactly the values previously held in the tree.

find :: (Tree a -> Bool) -> Tree a -> Maybe (Tree a) Source #

Find a subtree in the given tree (first argument) whose root matches the predicate (second argument).

findByNode :: (a -> Bool) -> Tree a -> Maybe (Tree a) Source #

Same as find but takes a predicate over elements instead of a predicate over trees to identify the subtree of interest.

parent :: Eq a => Tree a -> Tree a -> Maybe (Tree a) Source #

Returns the parent of the given node (second argument) in the given tree (first argument). The returned parent is a subtree of the first given tree and has the second given tree as child. Throws an error iff no parent exists.

ancestors :: Eq a => Tree a -> Tree a -> [Tree a] Source #

Retrieves all nodes that are above the given node (second argument) in the given tree (first argument) (This is the transitive closure of parent.)

manipulate :: (Tree a -> Tree a) -> Tree a -> Tree a Source #

Applies the given function to each node from bottom to top (i.e., leaves are converted first, root last).

filterTrees :: (Tree a -> Bool) -> Tree a -> Tree a Source #

Removes all subtrees not meeting the imposed condition. The root remains untouched.

filterNodes :: (Tree a -> Bool) -> Tree a -> Tree a Source #

Removes all nodes not meeting the imposed condition. Children of removed nodes are moved up and become children of the parent of the removed node. The root remains untouched.

prettyPrint :: (Show a, Monoid b) => Int -> (String -> b) -> (a -> b) -> Tree a -> b Source #

Pretty print function that folds the tree into a monoidial type b. b is the type that is the output of the print (e.g., String or Text). First argument is the length of the indent in spaces (e.g., 2 will produce an indent of " " per level). Second argument is a function that lifts strings to the output type b (e.g., a constructor of b accepting a string). Third argument is a function to convert tree elements to the output type (e.g., show if b is String).