2-- Module : Streamly.Internal.Data.Fold.Window
3-- Copyright : (c) 2020 Composewell Technologies
5-- Maintainer : streamly@composewell.com
6-- Stability : experimental
9-- Simple incremental statistical measures over a stream of data. All
10-- operations use numerically stable floating point arithmetic.
12-- Measurements can be performed over the entire input stream or on a sliding
13-- window of fixed or variable size. Where possible, measures are computed
14-- online without buffering the input stream.
16-- Currently there is no overflow detection.
18-- For more advanced statistical measures see the @streamly-statistics@
21module Streamly.Internal.Data.Fold.Window
23 -- * Incremental Folds
24 -- | Folds of type @Fold m (a, Maybe a) b@ are incremental sliding window
25 -- folds. An input of type @(a, Nothing)@ indicates that the input element
26 -- @a@ is being inserted in the window without ejecting an old value
27 -- increasing the window size by 1. An input of type @(a, Just a)@
28 -- indicates that the first element is being inserted in the window and the
29 -- second element is being removed from the window, the window size remains
30 -- the same. The window size can only increase and never decrease.
32 -- You can compute the statistics over the entire stream using sliding
33 -- window folds by keeping the second element of the input tuple as
54import Data.Bifunctor(bimap)
55import Data.Function ((&))
56import Data.Maybe (fromMaybe)
58import Streamly.Internal.Data.Fold.Type (Fold(..), Step(..))
59import Streamly.Internal.Data.Tuple.Strict (Tuple'(..), Tuple3'(..))
61import Prelude hiding (length, sum, minimum, maximum)
63import qualified Deque.Strict as DQ
64import qualified Streamly.Data.Fold as Fold
67-- >>> import Data.Bifunctor(bimap)
68-- >>> import qualified Streamly.Data.Fold as Fold
69-- >>> import Prelude hiding (length, sum, minimum, maximum)
71-------------------------------------------------------------------------------
73-------------------------------------------------------------------------------
75-- | Map a function on the incoming as well as outgoing element of a rolling
78-- >>> lmap f = Fold.lmap (bimap f (f <$>))
81lmap :: (c -> a) -> Fold m (a, Maybe a) b -> Fold m (c, Maybe c) b
82lmap f = Fold.lmap (bimap f (f <$>))
84-- | Convert an incremental fold to a cumulative fold using the entire input
85-- stream as a single window.
87-- >>> cumulative f = Fold.lmap (\x -> (x, Nothing)) f
89{-# INLINE cumulative #-}
90cumulative :: Fold m (a, Maybe a) b -> Fold m a b
91cumulative = Fold.lmap (, Nothing)
93-------------------------------------------------------------------------------
95-------------------------------------------------------------------------------
99-- | The sum of all the elements in a rolling window. The input elements are
100-- required to be intergal numbers.
102-- This was written in the hope that it would be a tiny bit faster than 'sum'
103-- for 'Integral' values. But turns out that 'sum' is 2% faster than this even
104-- for intergal values!
109sumInt :: forall m a. (Monad m, Integral a) => Fold m (a, Maybe a) a
110sumInt = Fold step initial extract
114 initial = return $ Partial (0 :: a)
121 Just old -> s + a - old
127-- | Sum of all the elements in a rolling window:
129-- \(S = \sum_{i=1}^n x_{i}\)
131-- This is the first power sum.
133-- >>> sum = powerSum 1
135-- Uses Kahan-Babuska-Neumaier style summation for numerical stability of
136-- floating precision arithmetic.
138-- /Space/: \(\mathcal{O}(1)\)
140-- /Time/: \(\mathcal{O}(n)\)
143sum :: forall m a. (Monad m, Num a) => Fold m (a, Maybe a) a
144sum = Fold step initial extract
152 (0 :: a) -- running sum
153 (0 :: a) -- accumulated rounding error
155 step (Tuple' total err) (new, mOld) =
158 -- XXX new may be large and err may be small we may lose it
160 -- XXX if (new - old) is large we may lose err
161 Just old -> (new - old) - err
162 -- total is large and incr may be small, we may round incr here but
163 -- we will accumulate the rounding error in err1 in the next step.
164 total1 = total + incr
165 -- Accumulate any rounding error in err1
166 -- XXX In the Nothing case above we may lose err, therefore we
167 -- should use ((total1 - total) - new) + err here.
168 -- Or even in the just case if (new - old) is large we may lose
169 -- err, so we should use ((total1 - total) + (old - new)) + err.
170 err1 = (total1 - total) - incr
171 in return $ Partial $ Tuple' total1 err1
173 extract (Tuple' total _) = return total
175-- | The number of elements in the rolling window.
177-- This is the \(0\)th power sum.
179-- >>> length = powerSum 0
182length :: (Monad m, Num b) => Fold m (a, Maybe a) b
183length = Fold.foldl' step 0
187 step w (_, Nothing) = w + 1
190-- | Sum of the \(k\)th power of all the elements in a rolling window:
192-- \(S_k = \sum_{i=1}^n x_{i}^k\)
194-- >>> powerSum k = lmap (^ k) sum
196-- /Space/: \(\mathcal{O}(1)\)
198-- /Time/: \(\mathcal{O}(n)\)
199{-# INLINE powerSum #-}
200powerSum :: (Monad m, Num a) => Int -> Fold m (a, Maybe a) a
201powerSum k = lmap (^ k) sum
203-- | Like 'powerSum' but powers can be negative or fractional. This is slower
204-- than 'powerSum' for positive intergal powers.
206-- >>> powerSumFrac p = lmap (** p) sum
208{-# INLINE powerSumFrac #-}
209powerSumFrac :: (Monad m, Floating a) => a -> Fold m (a, Maybe a) a
210powerSumFrac p = lmap (** p) sum
212-------------------------------------------------------------------------------
214-------------------------------------------------------------------------------
216-- Theoretically, we can approximate minimum in a rolling window by using a
217-- 'powerMean' with sufficiently large negative power.
219-- XXX If we need to know the minimum in the window only once in a while then
220-- we can use linear search when it is extracted and not pay the cost all the
223-- | The minimum element in a rolling window.
225-- If you want to compute the minimum of the entire stream Fold.minimum from
226-- streamly package would be much faster.
228-- /Time/: \(\mathcal{O}(n*w)\) where \(w\) is the window size.
230{-# INLINE minimum #-}
231minimum :: (Monad m, Ord a) => Fold m (a, Maybe a) a
232minimum = Fold step initial extract
236 initial = return $ Partial $ Tuple3' (0 :: Int) (0 :: Int)
237 (mempty :: DQ.Deque (Int, a))
239 step (Tuple3' i w q) (a, ma) =
242 return $ Partial $ Tuple3' (i + 1) (w + 1)
243 (headCheck i q (w + 1) & dqloop (i, a))
245 return $ Partial $ Tuple3' (i + 1) w
246 (headCheck i q w & dqloop (i,a))
248 {-# INLINE headCheck #-}
259 Nothing -> DQ.snoc ia q
260 -- XXX This can be improved for the case of `=`
266 extract (Tuple3' _ _ q) = return $ snd
267 $ fromMaybe (0, error "min: Empty stream")
270-- Theoretically, we can approximate maximum in a rolling window by using a
271-- 'powerMean' with sufficiently large positive power.
273-- | The maximum element in a rolling window.
275-- If you want to compute the maximum of the entire stream Fold.maximum from
276-- streamly package would be much faster.
278-- /Time/: \(\mathcal{O}(n*w)\) where \(w\) is the window size.
280{-# INLINE maximum #-}
281maximum :: (Monad m, Ord a) => Fold m (a, Maybe a) a
282maximum = Fold step initial extract
286 initial = return $ Partial $ Tuple3' (0 :: Int) (0 :: Int)
287 (mempty :: DQ.Deque (Int, a))
289 step (Tuple3' i w q) (a, ma) =
292 return $ Partial $ Tuple3' (i + 1) (w + 1)
293 (headCheck i q (w + 1) & dqloop (i, a))
295 return $ Partial $ Tuple3' (i + 1) w
296 (headCheck i q w & dqloop (i,a))
298 {-# INLINE headCheck #-}
309 Nothing -> DQ.snoc ia q
310 -- XXX This can be improved for the case of `=`
316 extract (Tuple3' _ _ q) =
319 $ fromMaybe (0, error "max: Empty stream")
322-- | Arithmetic mean of elements in a sliding window:
324-- \(\mu = \frac{\sum_{i=1}^n x_{i}}{n}\)
326-- This is also known as the Simple Moving Average (SMA) when used in the
327-- sliding window and Cumulative Moving Avergae (CMA) when used on the entire
330-- >>> mean = Fold.teeWith (/) sum length
332-- /Space/: \(\mathcal{O}(1)\)
334-- /Time/: \(\mathcal{O}(n)\)
336mean :: forall m a. (Monad m, Fractional a) => Fold m (a, Maybe a) a
337mean = Fold.teeWith (/) sum length
340-- | The difference between the maximum and minimum elements of a rolling window.
342-- >>> range = Fold.teeWith (-) maximum minimum
344-- If you want to compute the range of the entire stream @Fold.teeWith (-)
345-- Fold.maximum Fold.min@ from the streamly package would be much faster.
347-- /Space/: \(\mathcal{O}(n)\) where @n@ is the window size.
349-- /Time/: \(\mathcal{O}(n*w)\) where \(w\) is the window size.
352range :: (Monad m, Num a, Ord a) => Fold m (a, Maybe a) a
353range = Fold.teeWith (-) maximum minimum
keysesc to close
- j k
- move down, up
- enter
- open
- esc
- back, or up a level
- 1 2 3 4
- readme, files, commits, refs
- /
- filter
- y
- copy the clone command
- c
- compare the chosen commit with another (or shift-click both)
- ?
- show or hide this list