combinat-0.2.8.2: Generate and manipulate various combinatorial objects.

Math.Combinat.Trees.Nary

Description

N-ary trees.

Synopsis

# Types

module Data.Tree

data Tree a :: * -> * #

Multi-way trees, also known as rose trees.

Constructors

 Node FieldsrootLabel :: alabel valuesubForest :: Forest azero or more child trees

Instances

 Methods(>>=) :: Tree a -> (a -> Tree b) -> Tree b #(>>) :: Tree a -> Tree b -> Tree b #return :: a -> Tree a #fail :: String -> Tree a # Methodsfmap :: (a -> b) -> Tree a -> Tree b #(<$) :: a -> Tree b -> Tree a # Methodspure :: a -> Tree a #(<*>) :: Tree (a -> b) -> Tree a -> Tree b #(*>) :: Tree a -> Tree b -> Tree b #(<*) :: Tree a -> Tree b -> Tree a # Methodsfold :: Monoid m => Tree m -> 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 # Methodstraverse :: 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) Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Data a => Data (Tree a) Methodsgfoldl :: (forall d b. Data d => c (d -> b) -> d -> c b) -> (forall g. g -> c g) -> Tree a -> c (Tree a) #gunfold :: (forall b r. Data b => c (b -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tree a) #toConstr :: Tree a -> Constr #dataTypeOf :: Tree a -> DataType #dataCast1 :: Typeable (* -> *) t => (forall d. Data d => c (t d)) -> Maybe (c (Tree a)) #dataCast2 :: Typeable (* -> * -> *) t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tree a)) #gmapT :: (forall b. Data b => b -> b) -> Tree a -> Tree a #gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r #gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tree a -> r #gmapQ :: (forall d. Data d => d -> u) -> Tree a -> [u] #gmapQi :: Int -> (forall d. Data d => d -> u) -> Tree a -> u #gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) #gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) #gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tree a -> m (Tree a) # Read a => Read (Tree a) MethodsreadsPrec :: Int -> ReadS (Tree a) #readList :: ReadS [Tree a] # Show a => Show (Tree a) MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # NFData a => NFData (Tree a) Methodsrnf :: Tree a -> () # # Regular trees ternaryTrees :: Int -> [Tree ()] Source # Ternary trees on n nodes (synonym for regularNaryTrees 3) Arguments  :: Int degree = number of children of each node -> Int number of nodes -> [Tree ()] 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. Arguments  :: [Int] set of allowed number of children -> Int number of nodes -> [Tree ()] 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 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.

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

# Graphviz drawing

Arguments

 :: Show a => Bool reverse the direction of the arrow -> String name of the graph -> Tree a -> Dot

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

Arguments

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

classifyTreeNode :: Tree a -> Either a a Source #

Left is leaf, Right is node

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

The length (number of edges) on the left spine

leftSpineLength tree == length (leftSpine_ tree)

# Unique labels

addUniqueLabelsTree :: Tree a -> Tree (a, Int) Source #

Adds unique labels to the nodes (including leaves) of a Tree.

Adds unique labels to the nodes (including leaves) of a Forest

# Labelling by depth

labelDepthTree :: Tree a -> Tree (a, Int) Source #

Attaches the depth to each node. The depth of the root is 0.

# Labelling by number of children

labelNChildrenTree :: Tree a -> Tree (a, Int) Source #

Attaches the number of children to each node.

# Orphan instances

 DrawASCII (Tree ()) Source # Methodsascii :: Tree () -> ASCII Source # Source # Methods Source # Methods