online: online statistics

[ bsd3, library, project ] [ Propose Tags ]

transformation of statistics to online algorithms

[Skip to Readme]
Versions [RSS] [faq] 0.2.0,,,,,, 0.5.0, 0.6.0
Dependencies base (>=4.7 && <5), foldl, formatting, numhask-prelude, online, optparse-generic, perf, protolude, scientific, tdigest, text, vector, vector-algorithms [details]
License BSD-3-Clause
Copyright Tony Day
Author Tony Day
Category statistics
Home page
Bug tracker
Source repo head: git clone
Uploaded by tonyday567 at 2018-04-07T05:39:19Z
Distributions NixOS:0.6.0
Executables online-bench
Downloads 2924 total (42 in the last 30 days)
Rating (no votes yet) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Hackage Matrix CI
Docs not available [build log]
All reported builds failed as of 2021-06-02 [all 2 reports]


  • Online
    • Online.Averages
    • Online.Medians
    • Online.Quantiles


Maintainer's Corner

For package maintainers and hackage trustees


Readme for online-

[back to package description]


BuildStatus Hackage lts nightly

online turns a statistic (in haskell this can usually be thought of as a fold of a foldable) into an online algorithm.


Imagine a data stream, like an ordered indexed container or a time-series of measurements. An exponential moving average can be calculated as a repeated iteration over a stream of xs:

\[ ema_t = ema_{t-1} * 0.9 + x_t * 0.1 \]

The 0.1 is akin to the learning rate in machine learning, or 0.9 can be thought of as a decaying or a rate of forgetting. An exponential moving average learns about what the value of x has been lately, where lately is, on average, about 1/0.1 = 10 x's ago. All very neat.

The first bit of neat is speed. There's 2 times and a plus. The next is space: an ema is representing the recent xs in a size as big as a single x. Compare that with a simple moving average where you have to keep the history of the last n xs around to keep up (just try it).

It's so neat, it's probably a viable monoidal category all by itself.


Haskell allows us to abstract the compound ideas in an ema and create polymorphic routines over a wide variety of statistics, so that they all retain these properties of speed, space and rigour.

av xs = L.fold (online identity (.* 0.9)) xs
-- av [0..10] == 6.030559401413827
-- av [0..100] == 91.00241448887785

online identity (.* 0.9) is how you express an ema with a decay rate of 0.9.

online works for any statistic. Here's the construction of standard deviation using applicative style:

std :: Double -> L.Fold Double Double
std r = (\s ss -> sqrt (ss - s**2)) <$> ma r <*> sqma r
    ma r = online identity (.*r)
    sqma r = online (**2) (.*r)


1 cycle = 0.4 nanoseconds.

sum to 1,000
run                       first     2nd     3rd     4th     5th  40th %
sumInt [0..]            6.064e3 1.746e3 1.560e3 1.540e3 1.626e3  1.544e3 cycles
sumDouble [0..]         7.835e5 3.032e5 3.104e5 2.837e5 3.051e5  8.957e4 cycles
sumPoly [0..]           1.139e5 7.660e4 7.638e4 7.648e4 7.636e4  7.674e4 cycles
sum Int                 1.601e4 1.186e4 1.167e4 1.158e4 1.176e4  1.168e4 cycles
sum Double              2.756e4 1.189e4 1.158e4 1.163e4 1.158e4  1.159e4 cycles
sum Poly                1.170e4 1.172e4 1.163e4 1.166e4 1.158e4  1.164e4 cycles
fold sum                1.177e4 1.174e4 1.178e4 1.185e4 1.177e4  1.175e4 cycles
fold av                 2.935e4 1.190e4 1.181e4 1.182e4 1.177e4  1.181e4 cycles
fold ma                 1.289e4 1.202e4 1.205e4 1.203e4 1.206e4  1.201e4 cycles
fold std                2.052e5 1.210e5 7.236e5 1.364e5 1.348e5  1.324e5 cycles
fold maL1               8.218e4 1.192e5 1.052e5 2.567e5 1.168e5  7.856e4 cycles
fold absmaL1            3.405e5 5.966e4 5.976e4 6.025e4 5.939e4  5.975e4 cycles


stack build --test --exec "$(stack path --local-install-root)/bin/online-bench" --exec "$(stack path --local-bin)/pandoc -f markdown -i other/ other/ other/ -t html -o index.html --filter pandoc-include --mathjax" --exec "$(stack path --local-bin)/pandoc -f markdown -i other/ -t markdown -o --filter pandoc-include --mathjax" --file-watch