Safe Haskell	None
Language	Haskell2010

Math.Combinat.Trees.Binary

Contents

Types
Conversion to rose trees (Data.Tree)
Enumerate leaves
Nested parentheses
Generating binary trees
ASCII drawing
Graphviz drawing
Bijections

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

data BinTree a
- = Branch (BinTree a) (BinTree a)
- | Leaf a
leaf :: BinTree ()
graft :: BinTree (BinTree a) -> BinTree a
data BinTree' a b
- = Branch' (BinTree' a b) b (BinTree' a b)
- | Leaf' a
forgetNodeDecorations :: BinTree' a b -> BinTree a
data Paren
- = LeftParen
- | RightParen
parenthesesToString :: [Paren] -> String
stringToParentheses :: String -> [Paren]
numberOfNodes :: HasNumberOfNodes t => t -> Int
numberOfLeaves :: HasNumberOfLeaves t => t -> Int
toRoseTree :: BinTree a -> Tree (Maybe a)
toRoseTree' :: BinTree' a b -> Tree (Either b a)
data Tree a = Node {
- rootLabel :: a
- subForest :: Forest a
}
type Forest a = [Tree a]
enumerateLeaves_ :: BinTree a -> BinTree Int
enumerateLeaves :: BinTree a -> BinTree (a, Int)
enumerateLeaves' :: BinTree a -> (Int, BinTree (a, Int))
nestedParentheses :: Int -> [[Paren]]
randomNestedParentheses :: RandomGen g => Int -> g -> ([Paren], g)
nthNestedParentheses :: Int -> Integer -> [Paren]
countNestedParentheses :: Int -> Integer
fasc4A_algorithm_P :: Int -> [[Paren]]
fasc4A_algorithm_W :: RandomGen g => Int -> g -> ([Paren], g)
fasc4A_algorithm_U :: Int -> Integer -> [Paren]
binaryTrees :: Int -> [BinTree ()]
countBinaryTrees :: Int -> Integer
binaryTreesNaive :: Int -> [BinTree ()]
randomBinaryTree :: RandomGen g => Int -> g -> (BinTree (), g)
fasc4A_algorithm_R :: RandomGen g => Int -> g -> (BinTree' Int Int, g)
asciiBinaryTree_ :: BinTree a -> ASCII
type Dot = String
graphvizDotBinTree :: Show a => String -> BinTree a -> Dot
graphvizDotBinTree' :: (Show a, Show b) => String -> BinTree' a b -> Dot
graphvizDotForest :: Show a => Bool -> Bool -> String -> Forest a -> Dot
graphvizDotTree :: Show a => Bool -> String -> Tree a -> Dot
forestToNestedParentheses :: Forest a -> [Paren]
forestToBinaryTree :: Forest a -> BinTree ()
nestedParenthesesToForest :: [Paren] -> Maybe (Forest ())
nestedParenthesesToForestUnsafe :: [Paren] -> Forest ()
nestedParenthesesToBinaryTree :: [Paren] -> Maybe (BinTree ())
nestedParenthesesToBinaryTreeUnsafe :: [Paren] -> BinTree ()
binaryTreeToForest :: BinTree a -> Forest ()
binaryTreeToNestedParentheses :: BinTree a -> [Paren]

Types

data BinTree a Source #

A binary tree with leaves decorated with type a.

Constructors

Branch (BinTree a) (BinTree a)
Leaf a

Instances

Monad BinTree Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods (>>=) :: BinTree a -> (a -> BinTree b) -> BinTree b # (>>) :: BinTree a -> BinTree b -> BinTree b # return :: a -> BinTree a # fail :: String -> BinTree a #
Functor BinTree Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods fmap :: (a -> b) -> BinTree a -> BinTree b # (<$) :: a -> BinTree b -> BinTree a #
Applicative BinTree Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods pure :: 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 #
Foldable BinTree Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods fold :: Monoid m => BinTree m -> 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 #
Traversable BinTree Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods traverse :: 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 details Defined in Math.Combinat.Trees.Binary Methods (==) :: BinTree a -> BinTree a -> Bool # (/=) :: BinTree a -> BinTree a -> Bool #
Ord a => Ord (BinTree a) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods compare :: 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 details Defined in Math.Combinat.Trees.Binary Methods readsPrec :: Int -> ReadS (BinTree a) # readList :: ReadS [BinTree a] # readPrec :: ReadPrec (BinTree a) # readListPrec :: ReadPrec [BinTree a] #
Show a => Show (BinTree a) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods showsPrec :: Int -> BinTree a -> ShowS # show :: BinTree a -> String # showList :: [BinTree a] -> ShowS #
HasNumberOfLeaves (BinTree a) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods numberOfLeaves :: BinTree a -> Int Source #
HasNumberOfNodes (BinTree a) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods numberOfNodes :: BinTree a -> Int Source #
DrawASCII (BinTree ()) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods ascii :: BinTree () -> ASCII Source #

leaf :: BinTree () 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

(Eq b, Eq a) => Eq (BinTree' a b) Source #
Instance details Defined 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 details Defined in Math.Combinat.Trees.Binary Methods compare :: 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 details Defined in Math.Combinat.Trees.Binary Methods readsPrec :: Int -> ReadS (BinTree' a b) # readList :: ReadS [BinTree' a b] # readPrec :: ReadPrec (BinTree' a b) # readListPrec :: ReadPrec [BinTree' a b] #
(Show b, Show a) => Show (BinTree' a b) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods showsPrec :: Int -> BinTree' a b -> ShowS # show :: BinTree' a b -> String # showList :: [BinTree' a b] -> ShowS #
HasNumberOfLeaves (BinTree' a b) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods numberOfLeaves :: BinTree' a b -> Int Source #
HasNumberOfNodes (BinTree' a b) Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods numberOfNodes :: BinTree' a b -> Int Source #

forgetNodeDecorations :: BinTree' a b -> BinTree a Source #

data Paren Source #

Constructors

LeftParen
RightParen

Instances

Eq Paren Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods (==) :: Paren -> Paren -> Bool # (/=) :: Paren -> Paren -> Bool #
Ord Paren Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods compare :: Paren -> Paren -> Ordering # (<) :: Paren -> Paren -> Bool # (<=) :: Paren -> Paren -> Bool # (>) :: Paren -> Paren -> Bool # (>=) :: Paren -> Paren -> Bool # max :: Paren -> Paren -> Paren # min :: Paren -> Paren -> Paren #
Read Paren Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods readsPrec :: Int -> ReadS Paren # readList :: ReadS [Paren] # readPrec :: ReadPrec Paren # readListPrec :: ReadPrec [Paren] #
Show Paren Source #
Instance details Defined in Math.Combinat.Trees.Binary Methods showsPrec :: Int -> Paren -> ShowS # show :: Paren -> String # showList :: [Paren] -> ShowS #

parenthesesToString :: [Paren] -> String Source #

stringToParentheses :: String -> [Paren] Source #

numberOfNodes :: HasNumberOfNodes t => t -> Int Source #

numberOfLeaves :: HasNumberOfLeaves t => t -> Int Source #

Conversion to rose trees (`Data.Tree`)

toRoseTree :: BinTree a -> Tree (Maybe a) Source #

Convert a binary tree to a rose tree (from Data.Tree)

toRoseTree' :: BinTree' a b -> Tree (Either b a) Source #

data Tree a #

Multi-way trees, also known as rose trees.

Constructors

Node
Fields rootLabel :: a label value subForest :: Forest a zero or more child trees

Instances

Monad Tree
Instance details Defined in Data.Tree Methods (>>=) :: Tree a -> (a -> Tree b) -> Tree b # (>>) :: Tree a -> Tree b -> Tree b # return :: a -> Tree a # fail :: String -> Tree a #
Functor Tree
Instance details Defined in Data.Tree Methods fmap :: (a -> b) -> Tree a -> Tree b # (<$) :: a -> Tree b -> Tree a #
MonadFix Tree	Since: containers-0.5.11
Instance details Defined in Data.Tree Methods mfix :: (a -> Tree a) -> Tree a #
Applicative Tree
Instance details Defined in Data.Tree Methods pure :: 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 #
Foldable Tree
Instance details Defined in Data.Tree Methods fold :: 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 #
Traversable Tree
Instance details Defined in Data.Tree Methods traverse :: 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) #
Eq1 Tree	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftEq :: (a -> b -> Bool) -> Tree a -> Tree b -> Bool #
Ord1 Tree	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftCompare :: (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering #
Read1 Tree	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftReadsPrec :: (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] #
Show1 Tree	Since: containers-0.5.9
Instance details Defined in Data.Tree Methods liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tree a -> ShowS # liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tree a] -> ShowS #
MonadZip Tree
Instance details Defined in Data.Tree Methods mzip :: 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 details Defined in Data.Tree Methods (==) :: Tree a -> Tree a -> Bool # (/=) :: Tree a -> Tree a -> Bool #
Data a => Data (Tree a)
Instance details Defined in Data.Tree Methods gfoldl :: (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)
Instance details Defined in Data.Tree Methods readsPrec :: Int -> ReadS (Tree a) # readList :: ReadS [Tree a] # readPrec :: ReadPrec (Tree a) # readListPrec :: ReadPrec [Tree a] #
Show a => Show (Tree a)
Instance details Defined in Data.Tree Methods showsPrec :: Int -> Tree a -> ShowS # show :: Tree a -> String # showList :: [Tree a] -> ShowS #
Generic (Tree a)
Instance details Defined in Data.Tree Associated Types type Rep (Tree a) :: * -> * # Methods from :: Tree a -> Rep (Tree a) x # to :: Rep (Tree a) x -> Tree a #
NFData a => NFData (Tree a)
Instance details Defined in Data.Tree Methods rnf :: Tree a -> () #
HasNumberOfLeaves (Tree a) Source #
Instance details Defined in Math.Combinat.Trees.Nary Methods numberOfLeaves :: Tree a -> Int Source #
HasNumberOfNodes (Tree a) Source #
Instance details Defined in Math.Combinat.Trees.Nary Methods numberOfNodes :: Tree a -> Int Source #
DrawASCII (Tree ()) Source #
Instance details Defined in Math.Combinat.Trees.Nary Methods ascii :: Tree () -> ASCII Source #
Generic1 Tree
Instance details Defined in Data.Tree Associated Types type Rep1 Tree :: k -> * # Methods from1 :: Tree a -> Rep1 Tree a # to1 :: Rep1 Tree a -> Tree a #
type Rep (Tree a)	Since: containers-0.5.8
Instance details Defined in Data.Tree type Rep (Tree a) = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" 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	Since: containers-0.5.8
Instance details Defined in Data.Tree type Rep1 Tree = D1 (MetaData "Tree" "Data.Tree" "containers-0.5.11.0" 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

enumerateLeaves_ :: BinTree a -> BinTree Int Source #

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.

nthNestedParentheses :: Int -> Integer -> [Paren] Source #

Synonym for fasc4A_algorithm_U.

countNestedParentheses :: Int -> Integer Source #

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.

fasc4A_algorithm_U Source #

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.

countBinaryTrees :: Int -> Integer Source #

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

asciiBinaryTree_ :: BinTree a -> ASCII Source #

Draws a binary tree in ASCII, ignoring node labels.

Example:

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

Graphviz drawing

type Dot = String Source #

graphvizDotBinTree :: Show a => String -> BinTree a -> Dot Source #

graphvizDotBinTree' :: (Show a, Show b) => String -> BinTree' a b -> Dot Source #

graphvizDotForest Source #

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.

graphvizDotTree Source #

Arguments