combinat-0.2.10.1: Generate and manipulate various combinatorial objects.
Safe HaskellSafe-Inferred
LanguageHaskell2010

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

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

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 #

Functor BinTree Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

Methods

fmap :: (a -> b) -> BinTree a -> BinTree b #

(<$) :: a -> BinTree b -> BinTree a #

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 #

Read a => Read (BinTree a) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

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 #

DrawASCII (BinTree ()) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

Methods

ascii :: BinTree () -> ASCII Source #

HasNumberOfLeaves (BinTree a) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

HasNumberOfNodes (BinTree a) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

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 #

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
(Read b, Read a) => Read (BinTree' a b) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

(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

HasNumberOfNodes (BinTree' a b) Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

Methods

numberOfNodes :: BinTree' a b -> Int Source #

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

data Paren Source #

Constructors

LeftParen 
RightParen 

Instances

Instances details
Read Paren Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

Show Paren Source # 
Instance details

Defined in Math.Combinat.Trees.Binary

Methods

showsPrec :: Int -> Paren -> ShowS #

show :: Paren -> String #

showList :: [Paren] -> ShowS #

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 #

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 

Fields

Instances

Instances details
MonadFix Tree

Since: containers-0.5.11

Instance details

Defined in Data.Tree

Methods

mfix :: (a -> Tree a) -> Tree a #

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

Foldable Tree 
Instance details

Defined in Data.Tree

Methods

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

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 #

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

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 #

Functor Tree 
Instance details

Defined in Data.Tree

Methods

fmap :: (a -> b) -> Tree a -> Tree b #

(<$) :: a -> Tree b -> Tree a #

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 #

Generic1 Tree 
Instance details

Defined in Data.Tree

Associated Types

type Rep1 Tree :: k -> Type #

Methods

from1 :: forall (a :: k). Tree a -> Rep1 Tree a #

to1 :: forall (a :: k). Rep1 Tree a -> Tree a #

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

Generic (Tree a) 
Instance details

Defined in Data.Tree

Associated Types

type Rep (Tree a) :: Type -> Type #

Methods

from :: Tree a -> Rep (Tree a) x #

to :: Rep (Tree a) x -> Tree a #

Read a => Read (Tree a) 
Instance details

Defined in Data.Tree

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 #

DrawASCII (Tree ()) Source # 
Instance details

Defined in Math.Combinat.Trees.Nary

Methods

ascii :: Tree () -> ASCII Source #

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 #

NFData a => NFData (Tree a) 
Instance details

Defined in Data.Tree

Methods

rnf :: Tree a -> () #

Eq a => Eq (Tree a) 
Instance details

Defined in Data.Tree

Methods

(==) :: Tree a -> Tree a -> Bool #

(/=) :: Tree a -> Tree a -> Bool #

Ord a => Ord (Tree a)

Since: containers-0.6.5

Instance details

Defined in Data.Tree

Methods

compare :: Tree a -> Tree a -> Ordering #

(<) :: Tree a -> Tree a -> Bool #

(<=) :: Tree a -> Tree a -> Bool #

(>) :: Tree a -> Tree a -> Bool #

(>=) :: Tree a -> Tree a -> Bool #

max :: Tree a -> Tree a -> Tree a #

min :: Tree a -> Tree a -> Tree 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.6.5.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 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.6.5.1" 'False) (C1 ('MetaCons "Node" 'PrefixI 'True) (S1 ('MetaSel ('Just "rootLabel") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Just "subForest") 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [Tree a])))

type Forest a = [Tree a] #

This type synonym exists primarily for historical reasons.

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.

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

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

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

Bijections