Math.Combinat.Trees

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

Types

data BinTree a

Constructors

Branch (BinTree a) (BinTree a)

Leaf a

Instances

Eq a => Eq (BinTree a)

Ord a => Ord (BinTree a)

Read a => Read (BinTree a)

Show a => Show (BinTree a)

leaf :: BinTree ()

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

Synonym for fasc4A_algorithm_P.

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.

Binary trees

binaryTrees :: Int -> [BinTree ()]

Generates all binary trees with n nodes.

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.