Skip to content

HORIZON HASKELL Docs lts/ghc-10.0.x8fef28d2026-11-02Search packagesCtrl K

Theme: |

GHC 10.0.0.20260917 · lts/ghc-10.0.x · 8fef28d · 2026-11-02

Moduletdigest-0.3.1Haskell2010

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...

Contents

Construction
Population
Compression
Statistics
Percentile
Mean & Variance
CDF
Debug

Synopsis

data TDigest
value tdigest
value singleton
value insert
value insert'
value compress
value forceCompress
value minimumValue
value maximumValue
value median
value quantile
value mean
value variance
value stddev
value cdf
value icdf
value size
value valid
value validate
value debugPrint

Packagetdigest-0.3.1
Exports20
LanguageHaskell2010
LicenceBSD-3-Clause
SourceTree.hs

Construction

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, …

KnownNat comp => Reducer Double (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
Both cons and snoc are insert
Show (TDigest compression)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
KnownNat comp => Semigroup (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
KnownNat comp => Monoid (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
NFData (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
TDigest has only strict fields.
KnownNat comp => Binary (TDigest comp)Defined in tdigest-0.3.1 · Data.TDigest.Tree.Internal
TDigest isn't compressed after de-serialisation, but it can be still smaller.
HasHistogram (TDigest comp) MaybeDefined in tdigest-0.3.1 · Data.TDigest.Tree.Internal

valuetdigest :: (Foldable f, KnownNat comp) => f Double -> TDigest comp

Strict foldl' over Foldable structure.

Population

valuesingleton :: KnownNat comp => Double -> TDigest comp

Make a TDigest of a single data point.

valueinsert

:: KnownNat comp
=> Double
element
-> TDigest comp
-> TDigest comp

Insert single value into TDigest.

valueinsert'

:: KnownNat comp
=> Double
element
-> TDigest comp
-> 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

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.

valueforceCompress :: KnownNat comp => TDigest comp -> TDigest comp

Perform compression, even if current size says it's not necessary.

Statistics

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

valuemedian :: TDigest comp -> Maybe Double

Median, i.e. quantile 0.5.

valuequantile :: Double -> TDigest comp -> Maybe Double

Calculate quantile of a specific value.

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.

valuevariance :: TDigest comp -> Maybe Double

Variance.

valuestddev :: TDigest comp -> Maybe Double

Standard deviation, square root of variance.

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.

valueicdf :: Double -> TDigest comp -> Maybe Double

An alias for quantile

Debug

valuesize :: TDigest comp -> Int

valuevalid :: TDigest comp -> Bool

isRight . validate

valuevalidate :: TDigest comp -> Either String (TDigest comp)

Check various invariants in the TDigest tree.

valuedebugPrint :: TDigest comp -> IO ()

Output the TDigest tree.