Safe Haskell | None |
---|---|

Language | Haskell2010 |

N-ary trees.

- module Data.Tree
- data Tree a :: * -> * = Node {}
- 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 ()]
- asciiTreeVertical_ :: Tree a -> ASCII
- asciiTreeVertical :: Show a => Tree a -> ASCII
- asciiTreeVerticalLeavesOnly :: Show a => Tree a -> ASCII
- type Dot = String
- graphvizDotTree :: Show a => Bool -> String -> Tree a -> Dot
- graphvizDotForest :: Show a => Bool -> Bool -> String -> Forest a -> Dot
- 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

# Types

module Data.Tree

data Tree a :: * -> *

Multi-way trees, also known as *rose trees*.

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

autoTabulate RowMajor (Right 5) $ map asciiTreeVertical $ map labelNChildrenTree_ $ semiRegularTrees [2,3] 2 [ 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

asciiTreeVertical_ :: Tree a -> ASCII Source

Vertical ASCII drawing of a tree, without labels. Example:

autoTabulate RowMajor (Right 5) $ map asciiTreeVertical_ $ regularNaryTrees 2 4

Nodes are denoted by `@`

, leaves by `*`

.

asciiTreeVertical :: Show a => Tree a -> ASCII Source

Prints all labels. Example:

asciiTreeVertical $ addUniqueLabelsTree_ $ (regularNaryTrees 3 9) !! 666

Nodes are denoted by `(label)`

, leaves by `label`

.

asciiTreeVerticalLeavesOnly :: Show a => Tree a -> ASCII Source

Prints the labels for the leaves, but not for the nodes.

# Graphviz drawing

Generates graphviz `.dot`

file from a tree. The first argument is
the name of the graph.

:: Show a | |

=> Bool | make the individual trees clustered subgraphs |

-> Bool | reverse the direction of the arrows |

-> String | name of the graph |

-> Forest a | |

-> Dot |

Generates graphviz `.dot`

file from a forest. The first argument tells whether
to make the individual trees clustered subgraphs; the second is the name of the
graph.

# 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