Safe Haskell  None 

Language  Haskell2010 
A data structure for a static forest.
 data TreeOrder
 data Forest p v a where
 forestWith :: Vector v a => (forall a. [Tree a] > [a]) > [Tree a] > Forest (p :: TreeOrder) v a
 forestPre :: Vector v a => [Tree a] > Forest Pre v a
 forestPost :: Vector v a => [Tree a] > Forest Post v a
 addIndices :: Int > Tree a > Tree (Int, a)
 addIndicesF :: Int > [Tree a] > [Tree (Int, a)]
 addIndicesF' :: Int > [Tree a] > [Tree Int]
 parentChildrenF :: Int > [Tree (Int, a)] > [Tree (Int, Int, [Int], a)]
 lrSiblingF :: [Tree (Int, a)] > Map Int (Int, Int)
 lrSibling :: Tree (Int, a) > Map Int (Int, Int)
 leftMostLeaves :: Forest p v a > Vector Int
 leftMostLeaf :: Forest p v a > Int > Int
 rightMostLeaves :: Forest p v a > Vector Int
 rightMostLeaf :: Forest p v a > Int > Int
 leftKeyRoots :: Forest Post v a > Vector Int
 sortedSubForests :: Forest p v a > [Vector Int]
 newtype Srt = Srt {}
 forestToTrees :: Forest p v a > Forest a
 newtype QCTree a = QCTree {}
 test1 :: [Tree Char]
 test2 :: [Tree Char]
 runtest :: [Tree Char] > IO ()
Documentation
Kind of possible TreeOrder
s.
TODO In
for inorder traversal?
TODO Unordered
for trees that have no sorted order?
data Forest p v a where Source #
A static forest structure. While traversals are always explicitly
possible by following the indices, the nodes themselves shall always be
ordered by the type p :: TreeOrder
. This is not completely enforced,
given that Forest
is exporting the constructor, but encouraged via
construction with helper functions. The labels of type a
(in label
)
require a vector structure v
for O(1)
access.
Forest :: Vector v a => {..} > Forest p v a  

forestWith :: Vector v a => (forall a. [Tree a] > [a]) > [Tree a] > Forest (p :: TreeOrder) v a Source #
Construct a static Forest
with a tree traversal function. I.e.
forestWith preorderF trees
will construct a preorder forest from the
list of trees
.
Siblings span trees in the forest!
addIndices :: Int > Tree a > Tree (Int, a) Source #
Add preordered
(!)
indices. First argument is the starting index.
addIndicesF :: Int > [Tree a] > [Tree (Int, a)] Source #
Add preordered
(!)
indices, but to a forest.
addIndicesF' :: Int > [Tree a] > [Tree Int] Source #
Add preordered
(!)
indices to a forest, but throw the label away as
well.
parentChildrenF :: Int > [Tree (Int, a)] > [Tree (Int, Int, [Int], a)] Source #
Add parent + children information. Yields
(Index,Parent,[Child],Label)
. Parent is 1
if root node.
lrSiblingF :: [Tree (Int, a)] > Map Int (Int, Int) Source #
Return a map with all the nearest siblings for each node, for a forest.
lrSibling :: Tree (Int, a) > Map Int (Int, Int) Source #
Return a map with all the nearest siblings for each node, for a tree.
rightMostLeaf :: Forest p v a > Int > Int Source #
Given a tree, and a node index, return the rightmost leaf for the node.
leftKeyRoots :: Forest Post v a > Vector Int Source #
Return all left key roots. These are the nodes that have no (super) parent with the same leftmost leaf.
This function is somewhat specialized for tree editing.
TODO group by
sortedSubForests :: Forest p v a > [Vector Int] Source #
Returns the list of all sorted subsets of subforests in the forest. If the forest is given in preorder, then The subsets are returned in reversed preorder.
TODO turn this into newtype vectors
that enforce size >= 1
.
forestToTrees :: Forest p v a > Forest a Source #
Given a forest, return the list of trees that constitue the forest.
QuickCheck
Wrapped quickcheck instance for Tree
.