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

- data BinTree a
- leaf :: BinTree ()
- data BinTree' a b
- forgetNodeDecorations :: BinTree' a b -> BinTree a
- module Data.Tree
- data Paren
- = LeftParen
- | RightParen

- parenthesesToString :: [Paren] -> String
- stringToParentheses :: String -> [Paren]
- 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]
- nestedParentheses :: Int -> [[Paren]]
- randomNestedParentheses :: RandomGen g => Int -> g -> ([Paren], g)
- nthNestedParentheses :: Int -> Integer -> [Paren]
- countNestedParentheses :: Int -> Integer
- fasc4A_algorithm_P :: Int -> [[Paren]]
- fasc4A_algorithm_W :: RandomGen g => Int -> g -> ([Paren], g)
- fasc4A_algorithm_U :: Int -> Integer -> [Paren]
- binaryTrees :: Int -> [BinTree ()]
- countBinaryTrees :: Int -> Integer
- binaryTreesNaive :: Int -> [BinTree ()]
- randomBinaryTree :: RandomGen g => Int -> g -> (BinTree (), g)
- fasc4A_algorithm_R :: RandomGen g => Int -> g -> (BinTree' Int Int, g)

# Types

A binary tree with leaves decorated with type `a`

.

A binary tree with leaves and internal nodes decorated
with types `a`

and `b`

, respectively.

forgetNodeDecorations :: BinTree' a b -> BinTree aSource

module Data.Tree

parenthesesToString :: [Paren] -> StringSource

stringToParentheses :: String -> [Paren]Source

# Bijections

forestToNestedParentheses :: Forest a -> [Paren]Source

forestToBinaryTree :: Forest a -> BinTree ()Source

binaryTreeToForest :: BinTree a -> Forest ()Source

binaryTreeToNestedParentheses :: BinTree a -> [Paren]Source

# Nested parentheses

nestedParentheses :: Int -> [[Paren]]Source

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`

.

fasc4A_algorithm_P :: Int -> [[Paren]]Source

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

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

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

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

.

countBinaryTrees :: Int -> IntegerSource

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

.