Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell98 |

- data FTree a
- empty :: (a -> Double) -> (a -> a -> Ordering) -> FTree a
- insert :: a -> FTree a -> FTree a
- query :: a -> FTree a -> Val
- invQuery :: Val -> FTree a -> Maybe a
- toList :: FTree a -> [a]
- toFreqList :: FTree a -> [(Double, a)]
- fromList :: (a -> a -> Ordering) -> (a -> Val) -> [a] -> FTree a
- size :: FTree a -> Int
- depth :: FTree a -> Int

# Documentation

Mother structure holds functions
that allow to get a value to be summed and comparison function.
Below there is a tree of `FNode`

s.

query :: a -> FTree a -> Val Source

Finds a cumulative sum up to a given node of a Fenwick tree. Note: if the node is not found, a sum at point corresponding to this node is still returned. (Convenient for finding CDF value at a given point.)

invQuery :: Val -> FTree a -> Maybe a Source

Finds a node corresponding to a given cumulative sum, convenient for sampling quantile function of a distribution. NOTE: returns an answer only up to a cumulative sum of a whole tree.

toFreqList :: FTree a -> [(Double, a)] Source

Extract a sorted list of cumulative sums, and corresponding objects from the tree.