combinat-0.2.10.0: Generate and manipulate various combinatorial objects.

Math.Combinat.Trees.Binary

Description

Binary trees, forests, etc. See: Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 4A.

For example, here are all the binary trees on 4 nodes:

Synopsis

# Types

data BinTree a Source #

A binary tree with leaves decorated with type a.

Constructors

 Branch (BinTree a) (BinTree a) Leaf a

#### Instances

Instances details
 Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods(>>=) :: BinTree a -> (a -> BinTree b) -> BinTree b #(>>) :: BinTree a -> BinTree b -> BinTree b #return :: a -> BinTree a # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodsfmap :: (a -> b) -> BinTree a -> BinTree b #(<$) :: a -> BinTree b -> BinTree a # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodspure :: a -> BinTree a #(<*>) :: BinTree (a -> b) -> BinTree a -> BinTree b #liftA2 :: (a -> b -> c) -> BinTree a -> BinTree b -> BinTree c #(*>) :: BinTree a -> BinTree b -> BinTree b #(<*) :: BinTree a -> BinTree b -> BinTree a # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodsfold :: Monoid m => BinTree m -> m #foldMap :: Monoid m => (a -> m) -> BinTree a -> m #foldMap' :: Monoid m => (a -> m) -> BinTree a -> m #foldr :: (a -> b -> b) -> b -> BinTree a -> b #foldr' :: (a -> b -> b) -> b -> BinTree a -> b #foldl :: (b -> a -> b) -> b -> BinTree a -> b #foldl' :: (b -> a -> b) -> b -> BinTree a -> b #foldr1 :: (a -> a -> a) -> BinTree a -> a #foldl1 :: (a -> a -> a) -> BinTree a -> a #toList :: BinTree a -> [a] #null :: BinTree a -> Bool #length :: BinTree a -> Int #elem :: Eq a => a -> BinTree a -> Bool #maximum :: Ord a => BinTree a -> a #minimum :: Ord a => BinTree a -> a #sum :: Num a => BinTree a -> a #product :: Num a => BinTree a -> a # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodstraverse :: Applicative f => (a -> f b) -> BinTree a -> f (BinTree b) #sequenceA :: Applicative f => BinTree (f a) -> f (BinTree a) #mapM :: Monad m => (a -> m b) -> BinTree a -> m (BinTree b) #sequence :: Monad m => BinTree (m a) -> m (BinTree a) # Eq a => Eq (BinTree a) Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods(==) :: BinTree a -> BinTree a -> Bool #(/=) :: BinTree a -> BinTree a -> Bool # Ord a => Ord (BinTree a) Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodscompare :: BinTree a -> BinTree a -> Ordering #(<) :: BinTree a -> BinTree a -> Bool #(<=) :: BinTree a -> BinTree a -> Bool #(>) :: BinTree a -> BinTree a -> Bool #(>=) :: BinTree a -> BinTree a -> Bool #max :: BinTree a -> BinTree a -> BinTree a #min :: BinTree a -> BinTree a -> BinTree a # Read a => Read (BinTree a) Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsreadsPrec :: Int -> ReadS (BinTree a) # Show a => Show (BinTree a) Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsshowsPrec :: Int -> BinTree a -> ShowS #show :: BinTree a -> String #showList :: [BinTree a] -> ShowS # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods DrawASCII (BinTree ()) Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodsascii :: BinTree () -> ASCII Source # graft :: BinTree (BinTree a) -> BinTree a Source # The monadic join operation of binary trees data BinTree' a b Source # A binary tree with leaves and internal nodes decorated with types a and b, respectively. Constructors  Branch' (BinTree' a b) b (BinTree' a b) Leaf' a #### Instances Instances details  (Eq b, Eq a) => Eq (BinTree' a b) Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods(==) :: BinTree' a b -> BinTree' a b -> Bool #(/=) :: BinTree' a b -> BinTree' a b -> Bool # (Ord b, Ord a) => Ord (BinTree' a b) Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methodscompare :: BinTree' a b -> BinTree' a b -> Ordering #(<) :: BinTree' a b -> BinTree' a b -> Bool #(<=) :: BinTree' a b -> BinTree' a b -> Bool #(>) :: BinTree' a b -> BinTree' a b -> Bool #(>=) :: BinTree' a b -> BinTree' a b -> Bool #max :: BinTree' a b -> BinTree' a b -> BinTree' a b #min :: BinTree' a b -> BinTree' a b -> BinTree' a b # (Read b, Read a) => Read (BinTree' a b) Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsreadsPrec :: Int -> ReadS (BinTree' a b) #readList :: ReadS [BinTree' a b] #readPrec :: ReadPrec (BinTree' a b) # (Show b, Show a) => Show (BinTree' a b) Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsshowsPrec :: Int -> BinTree' a b -> ShowS #show :: BinTree' a b -> String #showList :: [BinTree' a b] -> ShowS # Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsnumberOfLeaves :: BinTree' a b -> Int Source # Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsnumberOfNodes :: BinTree' a b -> Int Source # data Paren Source # Constructors  LeftParen RightParen #### Instances Instances details  Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods(==) :: Paren -> Paren -> Bool #(/=) :: Paren -> Paren -> Bool # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods(<) :: Paren -> Paren -> Bool #(<=) :: Paren -> Paren -> Bool #(>) :: Paren -> Paren -> Bool #(>=) :: Paren -> Paren -> Bool #max :: Paren -> Paren -> Paren #min :: Paren -> Paren -> Paren # Source # Instance detailsDefined in Math.Combinat.Trees.Binary Methods Source # Instance detailsDefined in Math.Combinat.Trees.Binary MethodsshowsPrec :: Int -> Paren -> ShowS #show :: Paren -> String #showList :: [Paren] -> ShowS # # Conversion to rose trees (Data.Tree) toRoseTree :: BinTree a -> Tree (Maybe a) Source # Convert a binary tree to a rose tree (from Data.Tree) data Tree a # Non-empty, possibly infinite, multi-way trees; also known as rose trees. Constructors  Node FieldsrootLabel :: alabel valuesubForest :: Forest azero or more child trees #### Instances Instances details  Instance detailsDefined in Data.Tree Methods(>>=) :: Tree a -> (a -> Tree b) -> Tree b #(>>) :: Tree a -> Tree b -> Tree b #return :: a -> Tree a # Instance detailsDefined in Data.Tree Methodsfmap :: (a -> b) -> Tree a -> Tree b #(<$) :: a -> Tree b -> Tree a # Since: containers-0.5.11 Instance detailsDefined in Data.Tree Methodsmfix :: (a -> Tree a) -> Tree a # Instance detailsDefined in Data.Tree Methodspure :: a -> Tree a #(<*>) :: Tree (a -> b) -> Tree a -> Tree b #liftA2 :: (a -> b -> c) -> Tree a -> Tree b -> Tree c #(*>) :: Tree a -> Tree b -> Tree b #(<*) :: Tree a -> Tree b -> Tree a # Instance detailsDefined in Data.Tree Methodsfold :: Monoid m => Tree m -> m #foldMap :: Monoid m => (a -> m) -> Tree a -> 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 # Instance detailsDefined in Data.Tree 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) # Since: containers-0.5.9 Instance detailsDefined in Data.Tree MethodsliftEq :: (a -> b -> Bool) -> Tree a -> Tree b -> Bool # Since: containers-0.5.9 Instance detailsDefined in Data.Tree MethodsliftCompare :: (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering # Since: containers-0.5.9 Instance detailsDefined in Data.Tree MethodsliftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tree a) #liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tree a] #liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tree a) #liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tree a] # Since: containers-0.5.9 Instance detailsDefined in Data.Tree MethodsliftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tree a -> ShowS #liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS # Instance detailsDefined in Data.Tree Methodsmzip :: Tree a -> Tree b -> Tree (a, b) #mzipWith :: (a -> b -> c) -> Tree a -> Tree b -> Tree c #munzip :: Tree (a, b) -> (Tree a, Tree b) # Eq a => Eq (Tree a) Instance detailsDefined in Data.Tree Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Data a => Data (Tree a) Instance detailsDefined in Data.Tree 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 :: forall r r'. (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) Instance detailsDefined in Data.Tree MethodsreadsPrec :: Int -> ReadS (Tree a) #readList :: ReadS [Tree a] # Show a => Show (Tree a) Instance detailsDefined in Data.Tree MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # Generic (Tree a) Since: containers-0.5.8 Instance detailsDefined in Data.Tree Associated Typestype Rep (Tree a) :: Type -> Type # Methodsfrom :: Tree a -> Rep (Tree a) x #to :: Rep (Tree a) x -> Tree a # NFData a => NFData (Tree a) Instance detailsDefined in Data.Tree Methodsrnf :: Tree a -> () # Source # Instance detailsDefined in Math.Combinat.Trees.Nary Methods Source # Instance detailsDefined in Math.Combinat.Trees.Nary Methods DrawASCII (Tree ()) Source # Instance detailsDefined in Math.Combinat.Trees.Nary Methodsascii :: Tree () -> ASCII Source # Since: containers-0.5.8 Instance detailsDefined in Data.Tree Associated Typestype Rep1 Tree :: k -> Type # Methodsfrom1 :: forall (a :: k). Tree a -> Rep1 Tree a #to1 :: forall (a :: k). Rep1 Tree a -> Tree a # type Rep (Tree a) Instance detailsDefined in Data.Tree type Rep (Tree a) = D1 ('MetaData "Tree" "Data.Tree" "containers-0.6.2.1" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Forest a)))) type Rep1 Tree Instance detailsDefined in Data.Tree type Rep1 Tree = D1 ('MetaData "Tree" "Data.Tree" "containers-0.6.2.1" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) Par1 :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) ([] :.: Rec1 Tree)))

type Forest a = [Tree a] #

# Enumerate leaves

Enumerates the leaves a tree, starting from 0, ignoring old labels

enumerateLeaves :: BinTree a -> BinTree (a, Int) Source #

Enumerates the leaves a tree, starting from zero

enumerateLeaves' :: BinTree a -> (Int, BinTree (a, Int)) Source #

Enumerates the leaves a tree, starting from zero, and also returns the number of leaves

# Nested parentheses

nestedParentheses :: Int -> [[Paren]] Source #

Generates all sequences of nested parentheses of length 2n in lexigraphic order.

Synonym for fasc4A_algorithm_P.

randomNestedParentheses :: RandomGen g => Int -> g -> ([Paren], g) Source #

Synonym for fasc4A_algorithm_W.

Synonym for fasc4A_algorithm_U.

fasc4A_algorithm_P :: Int -> [[Paren]] Source #

Generates all sequences of nested parentheses of length 2n. Order is lexicographical (when right parentheses are considered smaller then left ones). Based on "Algorithm P" in Knuth, but less efficient because of the "idiomatic" code.

fasc4A_algorithm_W :: RandomGen g => Int -> g -> ([Paren], g) Source #

Generates a uniformly random sequence of nested parentheses of length 2n. Based on "Algorithm W" in Knuth.

Arguments

 :: Int n -> Integer N; should satisfy 1 <= N <= C(n) -> [Paren]

Nth sequence of nested parentheses of length 2n. The order is the same as in fasc4A_algorithm_P. Based on "Algorithm U" in Knuth.

# Generating binary trees

binaryTrees :: Int -> [BinTree ()] Source #

Generates all binary trees with n nodes. At the moment just a synonym for binaryTreesNaive.

# = Catalan(n) = \frac { 1 } { n+1 } \binom { 2n } { n }.

This is also the counting function for forests and nested parentheses.

binaryTreesNaive :: Int -> [BinTree ()] Source #

Generates all binary trees with n nodes. The naive algorithm.

randomBinaryTree :: RandomGen g => Int -> g -> (BinTree (), g) Source #

Generates an uniformly random binary tree, using fasc4A_algorithm_R.

fasc4A_algorithm_R :: RandomGen g => Int -> g -> (BinTree' Int Int, g) Source #

Grows a uniformly random binary tree. "Algorithm R" (Remy's procudere) in Knuth. Nodes are decorated with odd numbers, leaves with even numbers (from the set [0..2n]). Uses mutable arrays internally.

# ASCII drawing

Draws a binary tree in ASCII, ignoring node labels.

Example:

autoTabulate RowMajor (Right 5) $map asciiBinaryTree_$ binaryTrees 4

# Graphviz drawing

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.

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.