Math.Combinat.Trees.Binary

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

Types

data BinTree a

A binary tree with leaves decorated with type a.

Constructors

Branch (BinTree a) (BinTree a)

Leaf a

Instances

Functor BinTree

Foldable BinTree

Traversable BinTree

Eq a => Eq (BinTree a)

Ord a => Ord (BinTree a)

Read a => Read (BinTree a)

Show a => Show (BinTree a)

leaf :: BinTree ()

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 a, Eq b) => Eq (BinTree' a b)

(Ord a, Ord b) => Ord (BinTree' a b)

(Read a, Read b) => Read (BinTree' a b)

(Show a, Show b) => Show (BinTree' a b)

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)

forgetNodeDecorations :: BinTree' a b -> BinTree a

module Data.Tree

data Paren

Constructors

LeftParen

RightParen

Instances

Eq Paren

Ord Paren

Read Paren

Show Paren

parenthesesToString :: [Paren] -> String

stringToParentheses :: String -> [Paren]

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]

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 lexigraphic (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.

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

printBinaryTree_ :: BinTree a -> IO ()

Draws a binary tree in ASCII, ignoring node labels.

Example:

 mapM_ printBinaryTree_ $ binaryTrees 4

drawBinaryTree_ :: BinTree a -> String