```{-| This module provides incremental statistics folds based upon the foldl library

>>> import Control.Foldl.Incremental
>>> import qualified Control.Foldl as L

The folds represent incremental statistics such as `moving averages`.

Statistics are based on exponential-weighting schemes which enable statistics to be calculated in a streaming one-pass manner.  The stream of moving averages with a `rate` of 0.9 is:

>>> scan (incMa 0.9) [1..10]

or if you just want the moving average at the end.

>>> fold (incMa 0.9) [1..10]

-}

module Control.Foldl.Incremental (
-- * Increment
Increment(..)
, incrementalize
-- * common incremental folds
, incMa
, incAbs
, incSq
, incStd
-- * move to Foldl
, scan
-- * reexports
, module Data.Foldable
) where

import           Control.Applicative ((<\$>), (<*>))
import           Control.Foldl (Fold(..))
import           Data.Foldable (Foldable(..))
import qualified Data.Foldable as F

-- | An Increment is the incremental state within an exponential moving average fold.
data Increment = Increment
{ _adder   :: {-# UNPACK #-} !Double
, _counter :: {-# UNPACK #-} !Double
, _rate    :: {-# UNPACK #-} !Double
} deriving (Show)

{-| Incrementalize takes a function and turns it into a `Control.Foldl.Fold` where the step incremental is an Increment with a step function iso to a step in an exponential moving average calculation.

>>> incrementalize id

is a moving average of a foldable

>>> incrementalize (*2)

is a moving average of the square of a foldable

This lets you build an exponential standard deviation computation (using Foldl) as

>>> std r = (\s ss -> sqrt (ss - s**2)) <\$> incrementalize id r <*> incrementalize (*2) r

An exponential moving average approach (where `average` id abstracted to `function`) represents an efficient single-pass computation that attempts to keep track of a running average of some Foldable.

The rate is the parameter regulating the discount of current state and the introduction of the current value.

>>> incrementalize id 1

tracks the sum/average of an entire Foldable.

>>> incrementalize id 0

produces the latest value (ie current state is discounted to zero)

A exponential moving average with a duration of 10 (the average lag of the values effecting the calculation) is

>>> incrementalize id (1/10)

-}
incrementalize :: (a -> Double) -> Double -> Fold a Double
incrementalize f r =  Fold step (Increment 0 0 r) (\(Increment a c _) -> a / c)
where
step (Increment n d r') n' = Increment (r' * n + f n') (r' * d + 1) r'
{-# INLINABLE incrementalize #-}

-- | moving average fold
incMa :: Double -> Fold Double Double
incMa = incrementalize id
{-# INLINABLE incMa #-}

-- | moving absolute average
incAbs :: Double -> Fold Double Double
incAbs = incrementalize abs
{-# INLINABLE incAbs #-}

-- | moving average square
incSq :: Double -> Fold Double Double
incSq = incrementalize (\x -> x*x)
{-# INLINABLE incSq #-}

-- | moving standard deviation
incStd :: Double -> Fold Double Double
incStd rate = (\s ss -> sqrt (ss - s**2)) <\$> incMa rate <*> incSq rate
{-# INLINABLE incStd #-}

-- | Scan
scan :: (Foldable f) => Fold a b -> f a -> [b]
scan (Fold step begin done) as = F.foldr step' done' as begin'
where
step' x k z = k \$! (step (head z) x:z)
done' = map done . reverse
begin' = [begin]
{-# INLINABLE scan #-}
```