Safe Haskell	None
Language	Haskell2010

Data.TDigest.Tree.Internal

Contents

But*, the benefit vs. code explosion is not yet worth.

Description

Internals of TDigest.

Tree implementation is based on Adams’ Trees Revisited by Milan Straka http://fox.ucw.cz/papers/bbtree/bbtree.pdf

Synopsis

data TDigest (compression :: Nat)
- = Node !Size !Mean !Weight !Weight !(TDigest compression) !(TDigest compression)
- | Nil
getCentroids :: TDigest comp -> [Centroid]
totalWeight :: TDigest comp -> Weight
size :: TDigest comp -> Int
minimumValue :: TDigest comp -> Mean
maximumValue :: TDigest comp -> Mean
emptyTDigest :: TDigest comp
combineDigest :: KnownNat comp => TDigest comp -> TDigest comp -> TDigest comp
insertCentroid :: forall comp. KnownNat comp => Centroid -> TDigest comp -> TDigest comp
node :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp
balanceR :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp
balanceL :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp
node' :: Int -> Mean -> Weight -> Weight -> TDigest comp -> TDigest comp -> TDigest comp
singNode :: Mean -> Weight -> TDigest comp
combinedCentroid :: Mean -> Weight -> Mean -> Weight -> Centroid
threshold :: Double -> Double -> Double -> Double
compress :: forall comp. KnownNat comp => TDigest comp -> TDigest comp
forceCompress :: forall comp. KnownNat comp => TDigest comp -> TDigest comp
toMVector :: forall comp s. KnownNat comp => TDigest comp -> ST s (MVector s (Centroid, Double))
relMaxSize :: Int
absMaxSize :: Int
balOmega :: Int
balAlpha :: Int
debugPrint :: TDigest comp -> IO ()
valid :: TDigest comp -> Bool
validate :: TDigest comp -> Either String (TDigest comp)
insert :: KnownNat comp => Double -> TDigest comp -> TDigest comp
insert' :: KnownNat comp => Double -> TDigest comp -> TDigest comp
singleton :: KnownNat comp => Double -> TDigest comp
tdigest :: (Foldable f, KnownNat comp) => f Double -> TDigest comp

Documentation

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

Constructors

Node !Size !Mean !Weight !Weight !(TDigest compression) !(TDigest compression)	Tree node
Nil	Empty tree

Instances

KnownNat comp => Reducer Double (TDigest comp) #	Both `cons` and `snoc` are `insert`
Instance details Defined in Data.TDigest.Tree.Internal Methods unit :: Double -> TDigest comp # snoc :: TDigest comp -> Double -> TDigest comp # cons :: Double -> TDigest comp -> TDigest comp #
Show (TDigest compression) #
Instance details Defined in Data.TDigest.Tree.Internal Methods showsPrec :: Int -> TDigest compression -> ShowS # show :: TDigest compression -> String # showList :: [TDigest compression] -> ShowS #
KnownNat comp => Semigroup (TDigest comp) #
Instance details Defined in Data.TDigest.Tree.Internal Methods (<>) :: TDigest comp -> TDigest comp -> TDigest comp # sconcat :: NonEmpty (TDigest comp) -> TDigest comp # stimes :: Integral b => b -> TDigest comp -> TDigest comp #
KnownNat comp => Monoid (TDigest comp) #
Instance details Defined in Data.TDigest.Tree.Internal Methods mempty :: TDigest comp # mappend :: TDigest comp -> TDigest comp -> TDigest comp # mconcat :: [TDigest comp] -> TDigest comp #
KnownNat comp => Binary (TDigest comp) #	`TDigest` isn't compressed after de-serialisation, but it can be still smaller.
Instance details Defined in Data.TDigest.Tree.Internal Methods put :: TDigest comp -> Put # get :: Get (TDigest comp) # putList :: [TDigest comp] -> Put #
NFData (TDigest comp) #	`TDigest` has only strict fields.
Instance details Defined in Data.TDigest.Tree.Internal Methods rnf :: TDigest comp -> () #
HasHistogram (TDigest comp) Maybe #
Instance details Defined in Data.TDigest.Tree.Internal Methods histogram :: TDigest comp -> Maybe (NonEmpty HistBin) # totalWeight :: TDigest comp -> Weight #

But*, the benefit vs. code explosion is not yet worth.

getCentroids :: TDigest comp -> [Centroid] #

totalWeight :: TDigest comp -> Weight #

Total count of samples.

>>> totalWeight (tdigest [1..100] :: TDigest 5)
100.0

size :: TDigest comp -> Int #

minimumValue :: TDigest comp -> Mean #

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

>>> minimumValue (tdigest [1..100] :: TDigest 3)
1.0

maximumValue :: TDigest comp -> Mean #

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

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

emptyTDigest :: TDigest comp #

combineDigest :: KnownNat comp => TDigest comp -> TDigest comp -> TDigest comp #

insertCentroid :: forall comp. KnownNat comp => Centroid -> TDigest comp -> TDigest comp #

node :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp #

Constructor which calculates size and total weight.

balanceR :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp #

Balance after right insertion.

balanceL :: Mean -> Weight -> TDigest comp -> TDigest comp -> TDigest comp #

Balance after left insertion.

node' :: Int -> Mean -> Weight -> Weight -> TDigest comp -> TDigest comp -> TDigest comp #

Alias to Node

singNode :: Mean -> Weight -> TDigest comp #

Create singular node.

combinedCentroid :: Mean -> Weight -> Mean -> Weight -> Centroid #

Add two weighted means together.

threshold #

Arguments

:: Double	total weight
-> Double	quantile
-> Double	compression (1/δ)
-> Double

Calculate the threshold, i.e. maximum weight of centroid.

compress :: forall comp. 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.

forceCompress :: forall comp. KnownNat comp => TDigest comp -> TDigest comp #

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

toMVector #

Arguments

:: KnownNat comp
=> TDigest comp	t-Digest
-> ST s (MVector s (Centroid, Double))	return also a "space left in the centroid" value for "shuffling"

relMaxSize :: Int #

Relative size parameter. Hard-coded value: 25.

absMaxSize :: Int #

Absolute size parameter. Hard-coded value: 1000.

balOmega :: Int #

balAlpha :: Int #

debugPrint :: TDigest comp -> IO () #

Output the TDigest tree.

valid :: TDigest comp -> Bool #

isRight . validate

validate :: TDigest comp -> Either String (TDigest comp) #

Check various invariants in the TDigest tree.

insert #

Arguments

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

Insert single value into TDigest.

insert' #

Arguments

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

singleton :: KnownNat comp => Double -> TDigest comp #

Make a TDigest of a single data point.

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

Strict foldl' over Foldable structure.

>>> :set -XDataKinds