Safe Haskell | None |
---|---|
Language | Haskell98 |
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
- 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 a Source
module Data.Tree
parenthesesToString :: [Paren] -> String Source
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
nestedParenthesesToBinaryTreeUnsafe :: [Paren] -> BinTree () Source
binaryTreeToForest :: BinTree a -> Forest () Source
binaryTreeToNestedParentheses :: BinTree a -> [Paren] Source
Nested parentheses
nestedParentheses :: Int -> [[Paren]] Source
Generates all sequences of nested parentheses of length 2n
in
lexigraphic order.
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 lexicographical (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 -> Integer Source
# = 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 -> String Source