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
.