Safe Haskell | None |
---|

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 -> IntegerSource

# = \frac {1} {(2n+1} \binom {3n} {n}

countRegularNaryTrees :: (Integral a, Integral b) => a -> b -> IntegerSource

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 -> StringSource

Nodes are denoted by `@`

, leaves by `*`

.

drawTreeVertical :: Show a => Tree a -> StringSource

Nodes are denoted by `(label)`

, leaves by `label`

.

drawTreeVerticalLeavesOnly :: Show a => Tree a -> StringSource

Nodes are denoted by `@`

, leaves by `label`

.

# classifying nodes

isTreeLeaf :: Tree a -> Maybe aSource

isTreeNode :: Tree a -> Maybe aSource

isTreeLeaf_ :: Tree a -> BoolSource

isTreeNode_ :: Tree a -> BoolSource

treeNodeNumberOfChildren :: Tree a -> IntSource

# counting nodes

countTreeNodes :: Tree a -> IntSource

countTreeLeaves :: Tree a -> IntSource

countTreeLabelsWith :: (a -> Bool) -> Tree a -> IntSource

# 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 -> IntSource

The length (number of edges) on the left spine

leftSpineLength tree == length (leftSpine_ tree)

rightSpineLength :: Tree a -> IntSource

# 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 IntSource

addUniqueLabelsForest_ :: Forest a -> Forest IntSource

# 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 IntSource

labelDepthForest_ :: Forest a -> Forest IntSource

# 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 IntSource

labelNChildrenForest_ :: Forest a -> Forest IntSource