foldl-incremental (empty) → 0.1.0.0

raw patch · 7 files changed

+227/−0 lines, 7 filesdep +basedep +bytestringdep +criterionsetup-changed

Dependencies added: base, bytestring, criterion, foldl, foldl-incremental, tasty, tasty-golden, tasty-hunit, tasty-quickcheck

Files

• LICENSE +21/−0
• README.markdown +5/−0
• Setup.hs +4/−0
• foldl-incremental.cabal +59/−0
• src/Control/Foldl/Incremental.hs +110/−0
• test/bench.hs +15/−0
• test/test.hs +13/−0

@@ -0,0 +1,21 @@+The MIT License (MIT)++Copyright (c) 2014 Tony Day++Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.

@@ -0,0 +1,5 @@+Incremental Foldl's+==============++A haskell library of incremental folds, using the `foldl` library.+

@@ -0,0 +1,4 @@+import Distribution.Simple++main :: IO ()+main = defaultMain

@@ -0,0 +1,59 @@+name:                     foldl-incremental+version:                  0.1.0.0+synopsis:                 incremental folds +author:                   Tony Day+Maintainer:               tonyday+license:                  MIT+license-File:             LICENSE+copyright:                Copyright (c) Tony Day 2014+author:                   Tony Day+category:                 Control,Statistics+build-type:               Simple+stability:                Experimental+cabal-version:            >= 1.10+extra-source-files:       README.markdown+synopsis:                 incremental folds+description:+    `foldl-incremental` allows you to create incremental folds and scans such as moving averages or moving deviations.+    .+    It supplies `Incremental` which represents a state of an exponential moving average calculation, and `incrementalize`, which turns functions into suitable step functions.++Homepage:                 https://github.com/tonyday567/foldl-incremental+bug-reports:              https://github.com/tonyday567/foldl-incremental/issues+tested-With:              GHC==7.6.3+source-repository         head+  type:                   git+  location:               git://github.com/tonyday567/foldl-incremental.git++library+  exposed-modules:        Control.Foldl.Incremental++  build-depends:          base >= 4 && < 5,+                          foldl >= 1.0.3 && < 2+                          +  default-language:       Haskell2010+  hs-source-dirs:         src++test-suite test+  type:                   exitcode-stdio-1.0+  main-is:                test.hs+  default-language:       Haskell2010+  hs-source-dirs:         src, test+  build-depends:          base >= 4 && < 5,+                          bytestring >= 0.10.0.2,+                          foldl >= 1.0.3 && < 2,+                          tasty >= 0.7 && < 1,+                          tasty-golden >= 2.2.0.2 && < 3,+                          tasty-quickcheck >= 0.8,+                          tasty-hunit >= 0.4.1 && < 5,+                          foldl-incremental >= 0.1.0.0++benchmark bench+  type:                   exitcode-stdio-1.0+  main-is:                bench.hs+  default-language:       Haskell2010+  hs-source-dirs:         test+  build-depends:          base >= 4 && < 5,+                          foldl >= 1.0.3 && < 2,+                          criterion >= 0.10.0.0,+                          foldl-incremental >= 0.1.0.0

@@ -0,0 +1,110 @@+{-| 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 (ma 0.9) [1..10]++or if you just want the moving average at the end.++>>> fold (ma 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 #-}

@@ -0,0 +1,15 @@+{-# LANGUAGE RankNTypes, OverloadedStrings #-}++module Main where++import qualified BenchIncremental++import           Criterion.Main+import           Criterion.Config++main :: IO ()+main = defaultMainWith Main.config (return ()) $+       BenchIncremental.component 0.1 [1..100000]++config :: Config+config = defaultConfig  { cfgSamples = ljust 10 }

@@ -0,0 +1,13 @@+import qualified TestIncremental+import           Test.Tasty++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests = testGroup "Tests" [tests']++tests' :: TestTree+tests' = testGroup "tests"+  [ TestIncremental.quickTests+  ]