HMath.DataStructure¶
Module index · Numerical conventions
Description
Persistent finite range, queue, heap and streaming structures. Constructors are opaque. Indices and half-open ranges are checked. Persistent array updates copy storage; asymptotic logarithmic claims refer to arithmetic/comparisons.
On this page¶
| API | Purpose |
|---|---|
| Fenwick | Persistent exact-Integer prefix-sum tree with zero-based updates and half-open queries. |
| fenwick | Build an immutable Fenwick prefix-sum tree from at most 1048576 Integers. |
| fenwickAdd | Given zero-based index,delta,then Fenwick tree, return a new tree with that value incremented. |
| fenwickPrefix | Given exclusive end then tree, return exact sum over [0,end). |
| fenwickRange | Given lo,hi,then tree, return exact half-open sum over [lo,hi). |
| SegmentTree | Persistent exact-Integer range-sum tree. |
| segmentTree | Build an immutable Integer sum segment tree from at most 1048576 values. |
| segmentSet | Given zero-based index,new Integer,then segment tree, return an updated tree. |
| segmentRange | Given lo,hi,then segment tree, return Integer sum over [lo,hi). |
| SparseTable | Immutable precomputed range-minimum table for nonempty half-open queries. |
| sparseTable | Precompute range minima for at most 1048576 Integers. |
| sparseMinimum | Given lo,hi,then sparse table, return minimum over nonempty [lo,hi). |
| DisjointSparseTable | Immutable disjoint range-sum table supporting constant-query arithmetic. |
| disjointSparseTable | Suffix/prefix blocks for associative integer addition, O(n log n) build and O(1) arithmetic for nonempty queries. |
| disjointRange | Given lo,hi,then disjoint sparse sum table, return exact sum over [lo,hi). |
| monotonicMinima | Sliding minima using an increasing deque of indices; output windows are complete only. |
| nextGreater | For each list position, return Maybe index of its first strictly greater element to the right, using a monotone stack. |
| Heap | Leftist binary min heap, O(log n) mergeinsertdelete-min comparisons. |
| emptyHeap | Construct an empty persistent leftist min-heap. heapPop returns Nothing until values are inserted. |
| heapInsert | Given value then persistent min-heap, return a new heap containing it. |
| heapPop | Return Nothing for empty heap, otherwise Just (smallest value,remaining heap). |
| heapFromList | Build a persistent min-heap from a finite list, retaining all elements including duplicates. |
| BinaryHeap | Complete binary min heap in an array. |
| binaryHeap | Build an array-backed Integer min-heap from at most 1048576 values. |
| binaryInsert | Given Integer then binary heap, return a persistent updated min-heap. |
| binaryPop | Return Nothing if empty, otherwise the smallest Integer and a new binary heap containing the remaining values. |
| IndexedHeap | An indexed priority queue backed by an ordered map and a binary heap. |
| indexedHeap | Construct an empty indexed priority queue. |
| indexedSet | Given Int key,Integer priority,then indexed heap, set or replace that key's priority. |
| indexedPop | Return Just ((key,priority),remaining queue) for the minimum (priority,key) pair, or Nothing if empty. |
| UnionFind | Persistent disjoint-set partition of zero-based indices, constructed with unionFind and updated by union. |
| unionFind | Construct disjoint singleton sets for n zero-based elements, requiring n in [0,1048576]. |
| findRoot | Given element index then union-find structure, return representative root. |
| union | Given two valid indices then union-find, return a new structure merging their components by size. |
| connected | Given two indices then union-find, return whether their roots match. |
| components | Return all disjoint components as lists of zero-based element indices, including singleton sets. |
| Bloom | Immutable probabilistic membership filter; False is definitive and True may be a false positive. |
| bloom | Given bit count m in [1,1048576] then hash count k in [1,64], construct an empty Bloom filter. |
| bloomInsert | Given Word64 key then Bloom filter, set its k hash positions and return updated filter. |
| bloomMember | Test a Word64 key against all Bloom hash positions. |
| bloomFalsePositiveBound | Conservative union bound min(1,kn/m)^k under independent uniform query hashes, since at most kn bits can be occupied. |
| CountMin | Immutable frequency sketch with nonnegative updates and possible collision overestimation. |
| countMin | Given positive width and depth with product<=1048576, construct an empty count-min sketch. |
| countMinAdd | Given Word64 key,nonnegative Integer increment,then sketch, increment its hash counters. |
| countMinEstimate | Given Word64 key then sketch, return minimum associated counter as an Integer frequency estimate. |
| countMinErrorBound | (additive error, failure probability) under the uniform-hash model. |
| HyperLogLog | Immutable probabilistic distinct-cardinality sketch, constructed with hyperLogLog. |
| hyperLogLog | Construct an empty cardinality sketch from precision p in [4,16], using 2^p registers. |
| hllAdd | Given Word64 item then HyperLogLog sketch, hash and update its register maximum. |
| hllEstimate | HyperLogLog with linear-counting small-range correction. |
| Reservoir | Seeded bounded Algorithm-R stream sample state. |
| reservoir | Given sample capacity in [0,1048576] then Word64 seed, construct an empty deterministic Algorithm-R reservoir. |
| reservoirAdd | Algorithm R with rejection sampling (no modulo bias). |
| reservoirValues | Return retained reservoir sample values. |
| OnlineQuantiles | Exact online order statistics with an explicit memory cap. |
| onlineQuantiles | Given exact-storage cap in [0,1048576], create an empty online order-statistics container. |
| quantileAdd | Given finite Double then quantile container, insert in sorted order. |
| onlineQuantile | Given finite q in [0,1] then nonempty quantile container, linearly interpolate order statistics at q*(n-1). |
Documentation
Fenwick
Persistent exact-Integer prefix-sum tree with zero-based updates and half-open queries. Construct with fenwick.
fenwick
fenwick :: [Integer] -> Either MathError Fenwick Source #
Build an immutable Fenwick prefix-sum tree from at most 1048576 Integers. Oversized input fails; indices in public operations are zero based.
fenwickAdd
fenwickAdd :: Int -> Integer -> Fenwick -> Either MathError Fenwick Source #
Given zero-based index,delta,then Fenwick tree, return a new tree with that value incremented. Invalid index returns Left InvalidArgument.
fenwickPrefix
fenwickPrefix :: Int -> Fenwick -> Either MathError Integer Source #
Given exclusive end then tree, return exact sum over [0,end). Require 0<=end<=length; invalid bounds fail.
fenwickRange
fenwickRange :: Int -> Int -> Fenwick -> Either MathError Integer Source #
Given lo,hi,then tree, return exact half-open sum over [lo,hi). Invalid/reversed bounds fail; empty range gives zero.
SegmentTree
data SegmentTree Source #
Persistent exact-Integer range-sum tree. Construct with segmentTree; segmentSet returns a new version.
Instances
| Show SegmentTree Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> SegmentTree -> ShowS # show :: SegmentTree -> String # showList :: [SegmentTree] -> ShowS # | |
| Eq SegmentTree Source # | |
Defined in HMath.DataStructure | |
segmentTree
segmentTree :: [Integer] -> Either MathError SegmentTree Source #
Build an immutable Integer sum segment tree from at most 1048576 values. Invalid size fails; later queries use half-open bounds.
segmentSet
segmentSet :: Int -> Integer -> SegmentTree -> Either MathError SegmentTree Source #
Given zero-based index,new Integer,then segment tree, return an updated tree. Invalid index fails; the original remains unchanged.
segmentRange
segmentRange :: Int -> Int -> SegmentTree -> Either MathError Integer Source #
Given lo,hi,then segment tree, return Integer sum over [lo,hi). Invalid bounds fail; an empty range gives zero.
SparseTable
data SparseTable Source #
Immutable precomputed range-minimum table for nonempty half-open queries. Construct with sparseTable.
Instances
| Show SparseTable Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> SparseTable -> ShowS # show :: SparseTable -> String # showList :: [SparseTable] -> ShowS # | |
| Eq SparseTable Source # | |
Defined in HMath.DataStructure | |
sparseTable
sparseTable :: [Integer] -> Either MathError SparseTable Source #
Precompute range minima for at most 1048576 Integers. Return immutable sparse table; oversized input fails.
sparseMinimum
sparseMinimum :: Int -> Int -> SparseTable -> Either MathError Integer Source #
Given lo,hi,then sparse table, return minimum over nonempty [lo,hi). Out-of-range/reversed or empty bounds fail.
DisjointSparseTable
data DisjointSparseTable Source #
Immutable disjoint range-sum table supporting constant-query arithmetic. Construct with disjointSparseTable.
Instances
| Show DisjointSparseTable Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> DisjointSparseTable -> ShowS # show :: DisjointSparseTable -> String # showList :: [DisjointSparseTable] -> ShowS # | |
| Eq DisjointSparseTable Source # | |
Defined in HMath.DataStructure Methods (==) :: DisjointSparseTable -> DisjointSparseTable -> Bool # (/=) :: DisjointSparseTable -> DisjointSparseTable -> Bool # | |
disjointSparseTable
disjointSparseTable :: [Integer] -> Either MathError DisjointSparseTable Source #
Suffix/prefix blocks for associative integer addition, O(n log n) build and O(1) arithmetic for nonempty queries. Also handles an empty range as zero.
disjointRange
disjointRange :: Int -> Int -> DisjointSparseTable -> Either MathError Integer Source #
Given lo,hi,then disjoint sparse sum table, return exact sum over [lo,hi). Invalid bounds fail; empty range yields zero.
monotonicMinima
monotonicMinima :: Ord a => Int -> [a] -> Either MathError [a] Source #
Sliding minima using an increasing deque of indices; output windows are complete only. This list-backed reference deque has O(n*w) worst-case moves.
nextGreater
nextGreater :: Ord a => [a] -> [Maybe Int] Source #
For each list position, return Maybe index of its first strictly greater element to the right, using a monotone stack. Preserve input length; absent successors yield Nothing.
Heap
Leftist binary min heap, O(log n) mergeinsertdelete-min comparisons.
emptyHeap
Construct an empty persistent leftist min-heap. heapPop returns Nothing until values are inserted.
heapInsert
heapInsert :: Ord a => a -> Heap a -> Heap a Source #
Given value then persistent min-heap, return a new heap containing it. Duplicate values are retained; original heap remains valid.
heapPop
heapPop :: Ord a => Heap a -> Maybe (a, Heap a) Source #
Return Nothing for empty heap, otherwise Just (smallest value,remaining heap). Ties follow lawful Ord without discarding duplicates.
heapFromList
heapFromList :: Ord a => [a] -> Heap a Source #
Build a persistent min-heap from a finite list, retaining all elements including duplicates.
BinaryHeap
data BinaryHeap Source #
Complete binary min heap in an array. Persistence copies the backing array; sift operations make O(log n) comparisons.
Instances
| Show BinaryHeap Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> BinaryHeap -> ShowS # show :: BinaryHeap -> String # showList :: [BinaryHeap] -> ShowS # | |
| Eq BinaryHeap Source # | |
Defined in HMath.DataStructure | |
binaryHeap
binaryHeap :: [Integer] -> Either MathError BinaryHeap Source #
Build an array-backed Integer min-heap from at most 1048576 values. Oversized input fails.
binaryInsert
binaryInsert :: Integer -> BinaryHeap -> BinaryHeap Source #
Given Integer then binary heap, return a persistent updated min-heap. The insert operation itself has no Either size check.
binaryPop
binaryPop :: BinaryHeap -> Maybe (Integer, BinaryHeap) Source #
Return Nothing if empty, otherwise the smallest Integer and a new binary heap containing the remaining values.
IndexedHeap
data IndexedHeap Source #
An indexed priority queue backed by an ordered map and a binary heap. Updates lazily invalidate old heap entries; pop discards stale entries.
Instances
| Show IndexedHeap Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> IndexedHeap -> ShowS # show :: IndexedHeap -> String # showList :: [IndexedHeap] -> ShowS # | |
| Eq IndexedHeap Source # | |
Defined in HMath.DataStructure | |
indexedHeap
indexedHeap :: IndexedHeap Source #
Construct an empty indexed priority queue. Each Int key has at most one Integer priority.
indexedSet
indexedSet :: Int -> Integer -> IndexedHeap -> IndexedHeap Source #
Given Int key,Integer priority,then indexed heap, set or replace that key's priority. Return a new queue; an existing key is updated, not duplicated.
indexedPop
indexedPop :: IndexedHeap -> Maybe ((Int, Integer), IndexedHeap) Source #
Return Just ((key,priority),remaining queue) for the minimum (priority,key) pair, or Nothing if empty.
UnionFind
Persistent disjoint-set partition of zero-based indices, constructed with unionFind and updated by union.
unionFind
unionFind :: Int -> Either MathError UnionFind Source #
Construct disjoint singleton sets for n zero-based elements, requiring n in [0,1048576]. Invalid size fails.
findRoot
findRoot :: Int -> UnionFind -> Either MathError Int Source #
Given element index then union-find structure, return representative root. Invalid index fails; this pure query does not mutate/compress the stored structure.
union
union :: Int -> Int -> UnionFind -> Either MathError UnionFind Source #
Given two valid indices then union-find, return a new structure merging their components by size. Invalid indices fail; already connected inputs leave connectivity unchanged.
connected
connected :: Int -> Int -> UnionFind -> Either MathError Bool Source #
Given two indices then union-find, return whether their roots match. Invalid indices return Left InvalidArgument.
components
components :: UnionFind -> [[Int]] Source #
Return all disjoint components as lists of zero-based element indices, including singleton sets.
Bloom
Immutable probabilistic membership filter; False is definitive and True may be a false positive. Construct with bloom.
bloom
bloom :: Int -> Int -> Either MathError Bloom Source #
Given bit count m in [1,1048576] then hash count k in [1,64], construct an empty Bloom filter. Invalid dimensions fail.
bloomInsert
bloomInsert :: Word64 -> Bloom -> Bloom Source #
Given Word64 key then Bloom filter, set its k hash positions and return updated filter. Reinsertions are permitted; false positives remain possible.
bloomMember
bloomMember :: Word64 -> Bloom -> Bool Source #
Test a Word64 key against all Bloom hash positions. False means definitely absent; True may be a false positive under the documented hash model.
bloomFalsePositiveBound
bloomFalsePositiveBound :: Bloom -> Double Source #
Conservative union bound min(1,k*n/m)^k under independent uniform
query hashes, since at most k*n bits can be occupied. This is a bound rather
than the common exponential occupancy approximation.
CountMin
Immutable frequency sketch with nonnegative updates and possible collision overestimation. Construct with countMin.
Instances
countMin
countMin :: Int -> Int -> Either MathError CountMin Source #
Given positive width and depth with product<=1048576, construct an empty count-min sketch. Invalid dimensions fail.
countMinAdd
countMinAdd :: Word64 -> Integer -> CountMin -> Either MathError CountMin Source #
Given Word64 key,nonnegative Integer increment,then sketch, increment its hash counters. Negative updates fail; return a persistent updated sketch.
countMinEstimate
countMinEstimate :: Word64 -> CountMin -> Integer Source #
Given Word64 key then sketch, return minimum associated counter as an Integer frequency estimate. It may overestimate through collisions; use countMinErrorBound for the documented model.
countMinErrorBound
countMinErrorBound :: CountMin -> (Double, Double) Source #
(additive error, failure probability) under the uniform-hash model.
HyperLogLog
data HyperLogLog Source #
Immutable probabilistic distinct-cardinality sketch, constructed with hyperLogLog.
Instances
| Show HyperLogLog Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> HyperLogLog -> ShowS # show :: HyperLogLog -> String # showList :: [HyperLogLog] -> ShowS # | |
| Eq HyperLogLog Source # | |
Defined in HMath.DataStructure | |
hyperLogLog
hyperLogLog :: Int -> Either MathError HyperLogLog Source #
Construct an empty cardinality sketch from precision p in [4,16], using 2^p registers. Invalid precision fails; hllEstimate returns its probabilistic estimate.
hllAdd
hllAdd :: Word64 -> HyperLogLog -> HyperLogLog Source #
Given Word64 item then HyperLogLog sketch, hash and update its register maximum. Return persistent updated sketch; repeated items do not add a new exact count.
hllEstimate
hllEstimate :: HyperLogLog -> Double Source #
HyperLogLog with linear-counting small-range correction. Typical relative
standard error is approximately 1.04/sqrt(2^p) under uniform hashing.
Reservoir
Seeded bounded Algorithm-R stream sample state. Construct with reservoir and update with reservoirAdd.
reservoir
reservoir :: Int -> Word64 -> Either MathError (Reservoir a) Source #
Given sample capacity in [0,1048576] then Word64 seed, construct an empty deterministic Algorithm-R reservoir. Invalid capacity fails.
reservoirAdd
reservoirAdd :: a -> Reservoir a -> Either MathError (Reservoir a) Source #
Algorithm R with rejection sampling (no modulo bias). The 64-bit stream index is bounded; uniform sampling assumes the pseudorandom stream model.
reservoirValues
reservoirValues :: Reservoir a -> [a] Source #
Return retained reservoir sample values. Their count never exceeds capacity; output order is storage order, not a sorted or arrival-order guarantee.
OnlineQuantiles
data OnlineQuantiles Source #
Exact online order statistics with an explicit memory cap. This deliberately trades bounded-memory approximate quantiles for exact results; inserts are O(n), queries O(1) after insertion. Exceeding the cap fails without eviction.
Instances
| Show OnlineQuantiles Source # | |
Defined in HMath.DataStructure Methods showsPrec :: Int -> OnlineQuantiles -> ShowS # show :: OnlineQuantiles -> String # showList :: [OnlineQuantiles] -> ShowS # | |
| Eq OnlineQuantiles Source # | |
Defined in HMath.DataStructure Methods (==) :: OnlineQuantiles -> OnlineQuantiles -> Bool # (/=) :: OnlineQuantiles -> OnlineQuantiles -> Bool # | |
onlineQuantiles
onlineQuantiles :: Int -> Either MathError OnlineQuantiles Source #
Given exact-storage cap in [0,1048576], create an empty online order-statistics container. Invalid capacity fails; this retains exact values rather than a bounded-memory approximate sketch.
quantileAdd
quantileAdd :: Double -> OnlineQuantiles -> Either MathError OnlineQuantiles Source #
Given finite Double then quantile container, insert in sorted order. Non-finite values or a full cap fail without eviction; original container is unchanged.
onlineQuantile
onlineQuantile :: Double -> OnlineQuantiles -> Either MathError Double Source #
Given finite q in [0,1] then nonempty quantile container, linearly interpolate order statistics at q*(n-1). Invalid q or empty state returns Left InvalidArgument.