HORIZON HASKELLDocslts/ghc-9.10.x248f8f02026-10-05Search names, modules, packages, or :: a typeCtrl K

GHC 9.10.3 · lts/ghc-9.10.x · 248f8f0 · 2026-10-05

Moduletdigest-0.3Haskell2010

Data.TDigest.Tree

A new data structure for accurate on-line accumulation of rank-based statistics such as quantiles and trimmed means. . See original paper: "Computing extremely accurate quantiles using t-digest" by Ted Dunning and Otmar Ertl for more details https://github.com/tdunning/t-digest/blob/master/docs/t-digest-paper/histo.pdf.

Examples
Example1 expression
quantile 0.99 (tdigest [1..1000] :: TDigest 25)Just 990.5
Example1 expression
quantile 0.99 (tdigest [1..1000] :: TDigest 3)Just 989.0...

t-Digest is more precise in tails, especially median is imprecise:

Example1 expression
median (forceCompress $ tdigest [1..1000] :: TDigest 25)Just 497.6...
Semigroup

This operation isn't strictly associative, but statistical variables shouldn't be affected.

Example1 expression
let td xs = tdigest xs :: TDigest 10
Example1 expression
median (td [1..500] <> (td [501..1000] <> td [1001..1500]))Just 802...
Example1 expression
median ((td [1..500] <> td [501..1000]) <> td [1001..1500])Just 726...

The linear is worst-case scenario:

Example1 expression
let td' xs = tdigest (fairshuffle xs) :: TDigest 10
Example1 expression
median (td' [1..500] <> (td' [501..1000] <> td' [1001..1500]))Just 750.3789...
Example1 expression
median ((td' [1..500] <> td' [501..1000]) <> td' [1001..1500])Just 750.3789...
  • 1 type
  • 19 values
  • Packagetdigest-0.3
  • Exports20
  • LanguageHaskell2010
  • LicenceBSD-3-Clause
  • SourceTree.hs

Construction

2 declarations
datadata TDigest (compression :: Nat)
#

TDigest is a tree of centroids.

compression is a 1/δ. The greater the value of compression the less likely value merging will happen.

Instances7Reducer, Show, Semigroup, Monoid, NFData, Binary, …

Population

valueinsert'
  1. :: KnownNat comp
  2. => Double

    element

  3. -> TDigest comp
  4. -> TDigest comp
#

Insert single value, don't compress TDigest even if needed.

For sensibly bounded input, it makes sense to let TDigest grow (it might grow linearly in size), and after that compress it once.

Compression

2 declarations
Example2 expressions
let digest = foldl' (flip insert') mempty [0..1000] :: TDigest 10(size digest, size $ compress digest)(1001,52)
Example1 expression
(quantile 0.1 digest, quantile 0.1 $ compress digest)(Just 99.6...,Just 89.7...)

Note: when values are inserted in more random order, t-Digest self-compresses on the fly:

Example2 expressions
let digest = foldl' (flip insert') mempty (fairshuffle [0..1000]) :: TDigest 10(size digest, size $ compress digest, size $ forceCompress digest)(78,78,48)
Example1 expression
quantile 0.1 digestJust 98.9...
valuecompress :: KnownNat comp => TDigest comp -> TDigest comp
#

Compress TDigest.

Reinsert the centroids in "better" order (in original paper: in random) so they have opportunity to merge.

Compression will happen only if size is both: bigger than relMaxSize * comp and bigger than absMaxSize.

Statistics

2 declarations
valueminimumValue :: TDigest comp -> Mean
#

Center of left-most centroid. Note: may be different than min element inserted.

Example1 expression
minimumValue (tdigest [1..100] :: TDigest 3)1.0
valuemaximumValue :: TDigest comp -> Mean
#

Center of right-most centroid. Note: may be different than max element inserted.

Example1 expression
maximumValue (tdigest [1..100] :: TDigest 3)99.0

Percentile

Mean & Variance

  • - >>> stddev (tdigest $ fairshuffle [0..100] :: TDigest 10) Just 29.1...

valuemean :: TDigest comp -> Maybe Double
#

Mean.

Example1 expression
mean (tdigest [1..100] :: TDigest 10)Just 50.5

Note: if you only need the mean, calculate it directly.

CDF

valuecdf :: Double -> TDigest comp -> Double
#

Cumulative distribution function.

Note: if this is the only thing you need, it's more efficient to count this directly.

Debug

4 declarations