Safe Haskell | None |
---|
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
- toRoseTree :: BinTree a -> Tree (Maybe a)
- toRoseTree' :: BinTree' a b -> Tree (Either b a)
- 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)
- printBinaryTree_ :: BinTree a -> IO ()
- drawBinaryTree_ :: BinTree a -> String
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.
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
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
nestedParenthesesToForest :: [Paren] -> Maybe (Forest ())Source
nestedParenthesesToForestUnsafe :: [Paren] -> Forest ()Source
nestedParenthesesToBinaryTree :: [Paren] -> Maybe (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
.
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
printBinaryTree_ :: BinTree a -> IO ()Source
Draws a binary tree in ASCII, ignoring node labels.
Example:
mapM_ printBinaryTree_ $ binaryTrees 4
drawBinaryTree_ :: BinTree a -> StringSource