HMath.Algorithms¶
Module index · Numerical conventions
Description
Reference numerical search and ordering algorithms. Search routines validate
ascending input (O(n)); their subsequent search is logarithmic except ternary
optimization. Pure comparison sorts accept any lawful total Ord.
On this page¶
| API | Purpose |
|---|---|
| lowerBound | Given a target and ascending list, return the first zero-based insertion index whose value is >= target, or length at the end. |
| upperBound | Given a target and ascending list, return the first insertion index whose value is > target. |
| binarySearch | Given target and ascending list, return Just the first matching zero-based index or Nothing if absent. |
| interpolationSearch | Search ascending Integer values using value-based interpolation, returning the first matching index or Nothing. |
| exponentialSearch | Given a target and ascending finite list, grow a search range then find a matching index or Nothing. |
| ternarySearch | Fixed-iteration minimization of a unimodal finite function on [lo,hi]. |
| quickselect | Given a zero-based order-statistic index and list, return the element at that position in ascending order without returning a sorted list. |
| introselect | Like quickselect, but bound pivot depth and fall back to heap sorting. |
| partialSort | Given k in [0,length] and a list, return the k smallest values in ascending order, retaining duplicates. |
| mergeSort | Stable ascending merge sort under a lawful total Ord; accepts empty lists. |
| quicksort | Ascending reference quicksort preserving equal values, using the head as pivot. |
| heapsort | In-place-style array max heap with persistent updates. |
| introsort | Ascending comparison sort with bounded quickselect-style partition depth and heap-sort fallback. |
| countingSort | Given a nonnegative value-range budget then an Int list, return ascending counting sort. |
| radixSort | Sort unbounded Integers in ascending order by radix digits, separating negative and nonnegative magnitudes. |
| bucketSort | Given bucket count in [1,65536] and finite Doubles in [0,1], sort ascending using buckets and merge sort. |
| argsort | Return original zero-based indices in stable ascending value order. |
| topK | Alias of partialSort: return the k smallest values in ascending order, not the k largest. k outside [0,length] fails. |
| quantileSelect | Given finite q in [0,1] and a nonempty finite Double list, linearly interpolate the ascending order statistics at q*(n-1). |
| deduplicate | Sort ascending and keep one representative of each equal value. |
| numericGroups | Sort ascending and return each distinct value paired with its frequency. |
| runLengthEncode | Encode adjacent equal runs as (value,count), preserving run order without sorting. |
| runLengthDecode | Given maximum output length then (value,count) runs, expand runs. |
| prefixSums | Return cumulative sums including a leading zero; output length is n+1. |
| suffixSums | Return suffix sums including a final zero; output length is n+1. |
| differenceArray | Return first differences relative to a leading zero, preserving length. |
| applyDifferences | Reconstruct values from first differences by inclusive cumulative sum. |
| coordinateCompression | Return sorted unique keys and zero-based ranks for the original input order. |
| intervalSweep | Half-open interval union length and peak overlap; zero-length intervals contribute neither. |
| divideConquerDP | One DP layer next[j] = min_{0<=k<j} previous[k]+cost k j. |
| tabulateDP | Bottom-up bounded DAG recurrence; dependencies must have lower indices. |
| memoizedDP | Top-down memoization with a node budget. |
| binaryLift | K-fold application of a total finite successor map, by repeated squaring. |
| integerMatrixPower | Given square Integer rows and a nonnegative exponent, return exact matrix exponentiation by squaring; exponent zero returns identity. |
| polynomialHash | Given base, modulus >1, then Integer sequence, fold h=(h*base+x) mod modulus from zero. |
| rollingHashes | Noncryptographic polynomial rolling hash; equal hashes can collide. |
Documentation
lowerBound
lowerBound :: Ord a => a -> [a] -> Either MathError Int Source #
Given a target and ascending list, return the first zero-based insertion index whose value is >= target, or length at the end. Reject unsorted input. Validation is O(n). Example: lowerBound 2 [1,2,2,4] == Right 1.
upperBound
upperBound :: Ord a => a -> [a] -> Either MathError Int Source #
Given a target and ascending list, return the first insertion index whose value is > target. Reject unsorted input. Example: upperBound 2 [1,2,2,4] == Right 3.
binarySearch
binarySearch :: Ord a => a -> [a] -> Either MathError (Maybe Int) Source #
Given target and ascending list, return Just the first matching zero-based index or Nothing if absent. Reject unsorted input. Example: binarySearch 2 [1,2,2] == Right (Just 1).
interpolationSearch
interpolationSearch :: Integer -> [Integer] -> Either MathError (Maybe Int) Source #
Search ascending Integer values using value-based interpolation, returning the first matching index or Nothing. Reject unsorted input. Example: interpolationSearch 20 [10,20,30] == Right (Just 1).
exponentialSearch
exponentialSearch :: Ord a => a -> [a] -> Either MathError (Maybe Int) Source #
Given a target and ascending finite list, grow a search range then find a matching index or Nothing. Reject unsorted input. The implementation returns a matching index without a general first-duplicate guarantee.
ternarySearch
ternarySearch :: Int -> (Double -> Double) -> Double -> Double -> Either MathError (Double, Double) Source #
Fixed-iteration minimization of a unimodal finite function on [lo,hi]. Returns the final bracket; unimodality is a caller precondition.
quickselect
quickselect :: Ord a => Int -> [a] -> Either MathError a Source #
Given a zero-based order-statistic index and list, return the element at that position in ascending order without returning a sorted list. Reject negative/out-of-range indices. Example: quickselect 1 [9,1,5] == Right 5.
introselect
introselect :: Ord a => Int -> [a] -> Either MathError a Source #
Like quickselect, but bound pivot depth and fall back to heap sorting. Index must lie in [0,length). Example: introselect 0 [3,2,1] == Right 1.
partialSort
partialSort :: Ord a => Int -> [a] -> Either MathError [a] Source #
Given k in [0,length] and a list, return the k smallest values in ascending order, retaining duplicates. Invalid k fails. Example: partialSort 2 [5,1,3] == Right [1,3].
mergeSort
mergeSort :: Ord a => [a] -> [a] Source #
Stable ascending merge sort under a lawful total Ord; accepts empty lists. Return a new sorted list. Example: mergeSort [3,1,2] == [1,2,3].
quicksort
quicksort :: Ord a => [a] -> [a] Source #
Ascending reference quicksort preserving equal values, using the head as pivot. Worst-case quadratic work; accepts empty lists. Example: quicksort [2,1,2] == [1,2,2].
heapsort
heapsort :: Ord a => [a] -> [a] Source #
In-place-style array max heap with persistent updates. Correct heap sort; persistence adds allocation to the usual O(n log n) comparisons.
introsort
introsort :: Ord a => [a] -> [a] Source #
Ascending comparison sort with bounded quickselect-style partition depth and heap-sort fallback. Return a new sorted list; requires a lawful total Ord. Example: introsort [3,1,2] == [1,2,3].
countingSort
countingSort :: Int -> [Int] -> Either MathError [Int] Source #
Given a nonnegative value-range budget then an Int list, return ascending counting sort. Reject a negative budget or a range max-min+1 exceeding it (NonConvergence); empty input succeeds. Example: countingSort 5 [3,1,3] == Right [1,3,3].
radixSort
radixSort :: [Integer] -> [Integer] Source #
Sort unbounded Integers in ascending order by radix digits, separating negative and nonnegative magnitudes. Accepts empty input. Example: radixSort [2,-3,0] == [-3,0,2].
bucketSort
bucketSort :: Int -> [Double] -> Either MathError [Double] Source #
Given bucket count in [1,65536] and finite Doubles in [0,1], sort ascending using buckets and merge sort. Invalid count/data fail. Example: bucketSort 4 [1,0.5,0] == Right [0,0.5,1].
argsort
argsort :: Ord a => [a] -> [Int] Source #
Return original zero-based indices in stable ascending value order. Example: argsort [3,1,1] == [1,2,0]. No values are discarded.
topK
topK :: Ord a => Int -> [a] -> Either MathError [a] Source #
Alias of partialSort: return the k smallest values in ascending order, not the k largest. k outside [0,length] fails. Example: topK 2 [5,1,3] == Right [1,3].
quantileSelect
quantileSelect :: Double -> [Double] -> Either MathError Double Source #
Given finite q in [0,1] and a nonempty finite Double list, linearly interpolate the ascending order statistics at q*(n-1). Invalid data fail. Example: quantileSelect 0.5 [1,3] == Right 2.
deduplicate
deduplicate :: Ord a => [a] -> [a] Source #
Sort ascending and keep one representative of each equal value. Input order is not preserved. Example: deduplicate [3,1,3] == [1,3].
numericGroups
numericGroups :: Ord a => [a] -> [(a, Int)] Source #
Sort ascending and return each distinct value paired with its frequency. Example: numericGroups [2,1,2] == [(1,1),(2,2)].
runLengthEncode
runLengthEncode :: Eq a => [a] -> [(a, Int)] Source #
Encode adjacent equal runs as (value,count), preserving run order without sorting. Example: runLengthEncode [1,1,2,1] == [(1,2),(2,1),(1,1)].
runLengthDecode
runLengthDecode :: Int -> [(a, Int)] -> Either MathError [a] Source #
Given maximum output length then (value,count) runs, expand runs. Negative budget/count fails; output beyond the budget returns NonConvergence before allocation. Zero-length runs are allowed.
prefixSums
prefixSums :: Num a => [a] -> [a] Source #
Return cumulative sums including a leading zero; output length is n+1. Arithmetic follows Num. Example: prefixSums [1,2] == [0,1,3].
suffixSums
suffixSums :: Num a => [a] -> [a] Source #
Return suffix sums including a final zero; output length is n+1. Example: suffixSums [1,2] == [3,2,0].
differenceArray
differenceArray :: Num a => [a] -> [a] Source #
Return first differences relative to a leading zero, preserving length. Empty input gives empty output. Example: differenceArray [2,5,9] == [2,3,4].
applyDifferences
applyDifferences :: Num a => [a] -> [a] Source #
Reconstruct values from first differences by inclusive cumulative sum. Example: applyDifferences [2,3,4] == [2,5,9].
coordinateCompression
coordinateCompression :: Ord a => [a] -> ([a], [Int]) Source #
Return sorted unique keys and zero-based ranks for the original input order. Example: coordinateCompression [8,2,8] == ([2,8],[1,0,1]).
intervalSweep
intervalSweep :: [(Integer, Integer)] -> Either MathError (Integer, Int) Source #
Half-open interval union length and peak overlap; zero-length intervals contribute neither. End events precede starts at the same coordinate.
divideConquerDP
divideConquerDP :: [Double] -> (Int -> Int -> Double) -> Either MathError [Double] Source #
One DP layer next[j] = min_{0<=k<j} previous[k]+cost k j.
Monotone argmins are checked against all candidates before returning;
invalid optimization assumptions fail explicitly. O(n^2) validation.
tabulateDP
tabulateDP :: Int -> (Int -> [(Int, Integer)]) -> Either MathError [Integer] Source #
Bottom-up bounded DAG recurrence; dependencies must have lower indices.
memoizedDP
memoizedDP :: Int -> (Int -> (Integer, [(Int, Integer)])) -> Int -> Either MathError Integer Source #
Top-down memoization with a node budget. Recurrence supplies an additive constant and weighted dependencies; cycles are rejected.
binaryLift
binaryLift :: [Int] -> Integer -> Int -> Either MathError Int Source #
K-fold application of a total finite successor map, by repeated squaring.
integerMatrixPower
integerMatrixPower :: [[Integer]] -> Integer -> Either MathError [[Integer]] Source #
Given square Integer rows and a nonnegative exponent, return exact matrix exponentiation by squaring; exponent zero returns identity. Reject ragged/non-square matrices, order >128, or negative exponent.