Safe Haskell | None |
---|---|
Language | Haskell98 |
N-ary trees.
- ternaryTrees :: Int -> [Tree ()]
- regularNaryTrees :: Int -> Int -> [Tree ()]
- semiRegularTrees :: [Int] -> Int -> [Tree ()]
- countTernaryTrees :: Integral a => a -> Integer
- countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> Integer
- derivTrees :: [Int] -> [Tree ()]
- printTreeVertical_ :: Tree a -> IO ()
- printTreeVertical :: Show a => Tree a -> IO ()
- printTreeVerticalLeavesOnly :: Show a => Tree a -> IO ()
- drawTreeVertical_ :: Tree a -> String
- drawTreeVertical :: Show a => Tree a -> String
- drawTreeVerticalLeavesOnly :: Show a => Tree a -> String
- classifyTreeNode :: Tree a -> Either a a
- isTreeLeaf :: Tree a -> Maybe a
- isTreeNode :: Tree a -> Maybe a
- isTreeLeaf_ :: Tree a -> Bool
- isTreeNode_ :: Tree a -> Bool
- treeNodeNumberOfChildren :: Tree a -> Int
- countTreeNodes :: Tree a -> Int
- countTreeLeaves :: Tree a -> Int
- countTreeLabelsWith :: (a -> Bool) -> Tree a -> Int
- countTreeNodesWith :: (Tree a -> Bool) -> Tree a -> Int
- leftSpine :: Tree a -> ([a], a)
- leftSpine_ :: Tree a -> [a]
- rightSpine :: Tree a -> ([a], a)
- rightSpine_ :: Tree a -> [a]
- leftSpineLength :: Tree a -> Int
- rightSpineLength :: Tree a -> Int
- addUniqueLabelsTree :: Tree a -> Tree (a, Int)
- addUniqueLabelsForest :: Forest a -> Forest (a, Int)
- addUniqueLabelsTree_ :: Tree a -> Tree Int
- addUniqueLabelsForest_ :: Forest a -> Forest Int
- labelDepthTree :: Tree a -> Tree (a, Int)
- labelDepthForest :: Forest a -> Forest (a, Int)
- labelDepthTree_ :: Tree a -> Tree Int
- labelDepthForest_ :: Forest a -> Forest Int
- labelNChildrenTree :: Tree a -> Tree (a, Int)
- labelNChildrenForest :: Forest a -> Forest (a, Int)
- labelNChildrenTree_ :: Tree a -> Tree Int
- labelNChildrenForest_ :: Forest a -> Forest Int
regular trees
ternaryTrees :: Int -> [Tree ()] Source
Ternary trees on n
nodes (synonym for regularNaryTrees 3
)
regularNaryTrees d n
returns the list of (rooted) trees on n
nodes where each
node has exactly d
children. Note that the leaves do not count in n
.
Naive algorithm.
All trees on n
nodes where the number of children of all nodes is
in element of the given set. Example:
mapM_ printTreeVertical $ map labelNChildrenTree_ $ semiRegularTrees [2,3] n [ length $ semiRegularTrees [2,3] n | n<-[0..] ] == [1,2,10,66,498,4066,34970,312066,2862562,26824386,...]
The latter sequence is A027307 in OEIS: https://oeis.org/A027307
Remark: clearly, we have
semiRegularTrees [d] n == regularNaryTrees d n
countTernaryTrees :: Integral a => a -> Integer Source
# = \frac {1} {(2n+1} \binom {3n} {n}
countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> Integer Source
We have
length (regularNaryTrees d n) == countRegularNaryTrees d n == \frac {1} {(d-1)n+1} \binom {dn} {n}
derivation trees
derivTrees :: [Int] -> [Tree ()] Source
Computes the set of equivalence classes of rooted trees (in the
sense that the leaves of a node are unordered)
with n = length ks
leaves where the set of heights of
the leaves matches the given set of numbers.
The height is defined as the number of edges from the leaf to the root.
TODO: better name?
ASCII drawings
printTreeVertical_ :: Tree a -> IO () Source
Vertical ASCII drawing of a tree, without labels.
Example:
mapM_ printTreeVertical_ $ regularNaryTrees 2 3
printTreeVertical :: Show a => Tree a -> IO () Source
Prints all labels.
Example:
printTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666
printTreeVerticalLeavesOnly :: Show a => Tree a -> IO () Source
Prints the labels for the leaves, but not for the nonempty nodes
drawTreeVertical_ :: Tree a -> String Source
Nodes are denoted by @
, leaves by *
.
drawTreeVertical :: Show a => Tree a -> String Source
Nodes are denoted by (label)
, leaves by label
.
drawTreeVerticalLeavesOnly :: Show a => Tree a -> String Source
Nodes are denoted by @
, leaves by label
.
classifying nodes
isTreeLeaf :: Tree a -> Maybe a Source
isTreeNode :: Tree a -> Maybe a Source
isTreeLeaf_ :: Tree a -> Bool Source
isTreeNode_ :: Tree a -> Bool Source
treeNodeNumberOfChildren :: Tree a -> Int Source
counting nodes
countTreeNodes :: Tree a -> Int Source
countTreeLeaves :: Tree a -> Int Source
countTreeLabelsWith :: (a -> Bool) -> Tree a -> Int Source
left and right spines
leftSpine :: Tree a -> ([a], a) Source
The leftmost spine (the second element of the pair is the leaf node)
leftSpine_ :: Tree a -> [a] Source
The leftmost spine without the leaf node
rightSpine :: Tree a -> ([a], a) Source
rightSpine_ :: Tree a -> [a] Source
leftSpineLength :: Tree a -> Int Source
The length (number of edges) on the left spine
leftSpineLength tree == length (leftSpine_ tree)
rightSpineLength :: Tree a -> Int Source
unique labels
addUniqueLabelsTree :: Tree a -> Tree (a, Int) Source
Adds unique labels to the nodes (including leaves) of a Tree
.
addUniqueLabelsForest :: Forest a -> Forest (a, Int) Source
Adds unique labels to the nodes (including leaves) of a Forest
addUniqueLabelsTree_ :: Tree a -> Tree Int Source
addUniqueLabelsForest_ :: Forest a -> Forest Int Source
labelling by depth
labelDepthTree :: Tree a -> Tree (a, Int) Source
Attaches the depth to each node. The depth of the root is 0.
labelDepthForest :: Forest a -> Forest (a, Int) Source
labelDepthTree_ :: Tree a -> Tree Int Source
labelDepthForest_ :: Forest a -> Forest Int Source
labelling by number of children
labelNChildrenTree :: Tree a -> Tree (a, Int) Source
Attaches the number of children to each node.
labelNChildrenForest :: Forest a -> Forest (a, Int) Source
labelNChildrenTree_ :: Tree a -> Tree Int Source
labelNChildrenForest_ :: Forest a -> Forest Int Source