| Safe Haskell | Safe |
|---|---|
| Language | Haskell98 |
Combinatorics.TreeDepth
- nodeDepth :: [[Integer]]
- nodeDepthIt :: Integer -> [Integer] -> [Integer]
- type TreeFreq = Map [Integer] Integer
- treeDepth :: [Rational]
- treeDepthSeq :: [[Integer]]
- treePrototypes :: [TreeFreq]
- extendTree :: [Integer] -> [[Integer]]
- treeDepthIt :: TreeFreq -> TreeFreq
- nodeDegreeProb :: [[Rational]]
- nodeDegree :: [[Integer]]
- nodeDegreeIt :: Integer -> Integer -> [Integer] -> [Integer]
- nodeDegreeExpect :: [Rational]
- nodeDegreeExpectTrans :: Integer -> [Integer] -> [Integer]
- nodeDegreeExpectAux0 :: [Integer]
- nodeDegreeExpectAux1 :: [Integer]
Documentation
nodeDepth :: [[Integer]] Source #
nodeDepth !! n !! k is the absolute frequency
of nodes with depth k in trees with n nodes.
type TreeFreq = Map [Integer] Integer Source #
treeDepth !! n !! m !! k is the absolute frequency
of nodes with depth k in trees with n nodes and depth m.
This can't work - the function carries not enough information
for recursive definition.
treeDepth :: [[[Integer]]]
treeDepth = iterate (ls -> zipWith treeDepthIt ([[]]++ls) (ls++[[0]])) [[1]]
treeDepthIt :: [Integer] -> [Integer] -> [Integer] treeDepthIt nm0 nm1 = foldl1 add [scale (if null nm0 then 0 else last nm0) (nm0 ++ [1]), scale (sum (init nm1)) nm1, 0 : init nm1]
Trees are abstracted to lists of integers, where each integer denotes the number of nodes in the corresponding depth of the tree. The number associated with each tree is the frequency of this kind of tree on random tree generation.
treeDepthSeq :: [[Integer]] Source #
treePrototypes :: [TreeFreq] Source #
extendTree :: [Integer] -> [[Integer]] Source #
treeDepthIt :: TreeFreq -> TreeFreq Source #
nodeDegreeProb :: [[Rational]] Source #
nodeDegree !! n !! k is the number of nodes
with outdegree k in a n-node tree.
nodeDegree :: [[Integer]] Source #
nodeDegreeExpect :: [Rational] Source #
expected value of node degree