cabal-version: 3.0
name: dunning-t-digest
version: 0.1.0.0
synopsis: Dunning t-digest for online quantile estimation
description:
A pure functional implementation of the Dunning t-digest data structure
(merging digest variant, K1 arcsine scale function) using finger trees
with four-component monoidal measures for O(log n) insertion and queries.
.
Also provides a mutable variant backed by mutable vectors in the ST monad.
.
The t-digest provides streaming, mergeable, memory-bounded approximation
of quantile (percentile) queries with high accuracy in the tails.
.
Features:
.
* O(log n) insertion via split-by-mean (no buffering needed)
* O(log n) quantile queries via split-by-cumulative-weight
* O(log n) CDF queries via split-by-mean
* O(δ log n) compression via split-based greedy merge
* O(1) total weight, centroid count, and chunk mean computation
* Mutable variant with O(1) amortized insertion via buffering
license: BSD-3-Clause
license-file: LICENSE
author: Nadia Yvette Chambers
maintainer: nadia.yvette.chambers@gmail.com
copyright: (c) 2025 Nadia Yvette Chambers
category: Data, Statistics
build-type: Simple
extra-doc-files: CHANGELOG.md
tested-with: GHC == 9.14.1
source-repository head
type: git
location: https://github.com/NadiaYvette/t-digest.git
subdir: haskell
common warnings
ghc-options: -Wall
library
import: warnings
exposed-modules:
Data.Sketch.TDigest
Data.Sketch.TDigest.Mutable
build-depends:
, base >= 4.16 && < 5
, fingertree >= 0.1 && < 0.2
, vector >= 0.12 && < 0.14
hs-source-dirs: src
default-extensions:
MultiParamTypeClasses
RankNTypes
default-language: Haskell2010
executable dunning-t-digest-demo
import: warnings
main-is: Main.hs
build-depends:
, base >= 4.16 && < 5
, dunning-t-digest
hs-source-dirs: app
default-language: Haskell2010
executable dunning-t-digest-bench
import: warnings
main-is: Main.hs
build-depends:
, base >= 4.16 && < 5
, dunning-t-digest
hs-source-dirs: benchmarks
default-language: Haskell2010