Math.Combinat.Trees.Binary

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:

Types

data BinTree a

A binary tree with leaves decorated with type a.

Constructors

Branch (BinTree a) (BinTree a)

Leaf a

Instances

Monad BinTree

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

Defined in Math.Combinat.Trees.Binary

Methods

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

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

Applicative BinTree

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

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

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)

Defined in Math.Combinat.Trees.Binary

Methods

(==) :: BinTree a -> BinTree a -> Bool

(/=) :: BinTree a -> BinTree a -> Bool

Ord a => Ord (BinTree a)

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)

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)

Defined in Math.Combinat.Trees.Binary

Methods

showsPrec :: Int -> BinTree a -> ShowS

show :: BinTree a -> String

showList :: [BinTree a] -> ShowS

HasNumberOfLeaves (BinTree a)

Defined in Math.Combinat.Trees.Binary

Methods

numberOfLeaves :: BinTree a -> Int

HasNumberOfNodes (BinTree a)

Defined in Math.Combinat.Trees.Binary

Methods

numberOfNodes :: BinTree a -> Int

DrawASCII (BinTree ())

Defined in Math.Combinat.Trees.Binary

Methods

ascii :: BinTree () -> ASCII

leaf :: BinTree ()

graft :: BinTree (BinTree a) -> BinTree a

The monadic join operation of binary trees

data BinTree' a b

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)

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)

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)

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)

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)

Defined in Math.Combinat.Trees.Binary

Methods

numberOfLeaves :: BinTree' a b -> Int

HasNumberOfNodes (BinTree' a b)

Defined in Math.Combinat.Trees.Binary

Methods

numberOfNodes :: BinTree' a b -> Int

forgetNodeDecorations :: BinTree' a b -> BinTree a

data Paren

Constructors

LeftParen

RightParen

Instances

Eq Paren

Defined in Math.Combinat.Trees.Binary

Methods

(==) :: Paren -> Paren -> Bool

(/=) :: Paren -> Paren -> Bool

Ord Paren

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

Defined in Math.Combinat.Trees.Binary

Methods

readsPrec :: Int -> ReadS Paren

readList :: ReadS [Paren]

readPrec :: ReadPrec Paren

readListPrec :: ReadPrec [Paren]

Show Paren

Defined in Math.Combinat.Trees.Binary

Methods

showsPrec :: Int -> Paren -> ShowS

show :: Paren -> String

showList :: [Paren] -> ShowS

parenthesesToString :: [Paren] -> String

stringToParentheses :: String -> [Paren]

numberOfNodes :: HasNumberOfNodes t => t -> Int

numberOfLeaves :: HasNumberOfLeaves t => t -> Int

Conversion to rose trees (Data.Tree)

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

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

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

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

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

Defined in Data.Tree

Methods

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

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

MonadFix Tree

Since: containers-0.5.11

Defined in Data.Tree

Methods

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

Applicative Tree

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

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

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

Defined in Data.Tree

Methods

liftEq :: (a -> b -> Bool) -> Tree a -> Tree b -> Bool

Ord1 Tree

Since: containers-0.5.9

Defined in Data.Tree

Methods

liftCompare :: (a -> b -> Ordering) -> Tree a -> Tree b -> Ordering

Read1 Tree

Since: containers-0.5.9

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

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

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)

Defined in Data.Tree

Methods

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

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

Data a => Data (Tree a)

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)

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)

Defined in Data.Tree

Methods

showsPrec :: Int -> Tree a -> ShowS

show :: Tree a -> String

showList :: [Tree a] -> ShowS

Generic (Tree a)

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)

Defined in Data.Tree

Methods

rnf :: Tree a -> ()

HasNumberOfLeaves (Tree a)

Defined in Math.Combinat.Trees.Nary

Methods

numberOfLeaves :: Tree a -> Int

HasNumberOfNodes (Tree a)

Defined in Math.Combinat.Trees.Nary

Methods

numberOfNodes :: Tree a -> Int

DrawASCII (Tree ())

Defined in Math.Combinat.Trees.Nary

Methods

ascii :: Tree () -> ASCII

Generic1 Tree

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

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

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

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

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

Enumerates the leaves a tree, starting from zero

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

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

Nested parentheses

nestedParentheses :: Int -> [[Paren]]

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

Synonym for fasc4A_algorithm_P.

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

Synonym for fasc4A_algorithm_W.

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

Synonym for fasc4A_algorithm_U.

countNestedParentheses :: Int -> Integer

fasc4A_algorithm_P :: Int -> [[Paren]]

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)

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

fasc4A_algorithm_U

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 ()]

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

countBinaryTrees :: Int -> Integer

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

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

binaryTreesNaive :: Int -> [BinTree ()]

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

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

Generates an uniformly random binary tree, using fasc4A_algorithm_R.

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

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

Draws a binary tree in ASCII, ignoring node labels.

Example:

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

Graphviz drawing

type Dot = String

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

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

graphvizDotForest

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

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

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]