combinat-0.2.4.1: Generation of various combinatorial objects.Source codeContentsIndex
Math.Combinat.Trees.Binary
Contents
Types
Bijections
Nested parentheses
Binary trees
Description
Binary trees, forests, etc. See: Donald E. Knuth: The Art of Computer Programming, vol 4, pre-fascicle 4A.
Synopsis
data BinTree a
= Branch (BinTree a) (BinTree a)
| Leaf a
leaf :: BinTree ()
data BinTree' a b
= Branch' (BinTree' a b) b (BinTree' a b)
| Leaf' 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)
Types
data BinTree a Source
A binary tree with leaves decorated with type a.
Constructors
Branch (BinTree a) (BinTree a)
Leaf a
show/hide Instances
leaf :: BinTree ()Source
data BinTree' a b Source
A binary tree with leaves and internal nodes decorated with types a and b, respectively.
Constructors
Branch' (BinTree' a b) b (BinTree' a b)
Leaf' a
show/hide Instances
(Eq a, Eq b) => Eq (BinTree' a b)
(Ord a, Ord b) => Ord (BinTree' a b)
(Read a, Read b) => Read (BinTree' a b)
(Show a, Show b) => Show (BinTree' a b)
forgetNodeDecorations :: BinTree' a b -> BinTree aSource
module Data.Tree
data Paren Source
Constructors
LeftParen
RightParen
show/hide Instances
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
nestedParenthesesToBinaryTreeUnsafe :: [Paren] -> 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.
countNestedParentheses :: Int -> IntegerSource
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.
fasc4A_algorithm_USource
:: Intn
-> IntegerN; should satisfy 1 <= N <= C(n)
-> [Paren]
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.
Produced by Haddock version 2.6.1