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

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
Functor BinTree Source
Applicative BinTree Source
Foldable BinTree Source
Traversable BinTree Source
Eq a => Eq (BinTree a) Source
Ord a => Ord (BinTree a) Source
Read a => Read (BinTree a) Source
Show a => Show (BinTree a) Source
HasNumberOfLeaves (BinTree a) Source
HasNumberOfNodes (BinTree a) Source
DrawASCII (BinTree ()) 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 a, Eq b) => Eq (BinTree' a b) Source
(Ord a, Ord b) => Ord (BinTree' a b) Source
(Read a, Read b) => Read (BinTree' a b) Source
(Show a, Show b) => Show (BinTree' a b) Source
HasNumberOfLeaves (BinTree' a b) Source
HasNumberOfNodes (BinTree' a b) Source

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

data Paren Source

Constructors

LeftParen
RightParen

Instances

Eq Paren Source
Ord Paren Source
Read Paren Source
Show Paren Source

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

module Data.Tree

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