[Haskell-beginners] Simple Moving Average of a list of real numbers

[Michael Orlitzky]

On 11/26/2013 12:54 PM, Kim-Ee Yeoh wrote:
> 
> Hi Michael,
> 
> When I read OP's request, I understood it as what Ozgur had interpreted,
> i.e. last N items for a /constant/ N, also known as a moving window average.
> 
> Your running average solution is interesting too!

Oh, sorry. Statistics is down the hall =)

You need to modify the scanl1 solution a little bit, but it should still
work somewhat-efficiently only making one pass through the list and not
using any partial functions.

If the "window size" n is fixed, we need more information at each point
in the list:

  1. The item itself
  2. What number we should subtract from the previous sum
  3. What the previous divisor was
  4. What the new divisor is

(I'm assuming you want the first n items to be the running average, i.e.
my first implementation.)

The divisor that we'll use at each point is,

  [1, 2, ..., n, n, n...]

and that can be zipped with the samples just like before. The other
thing that we need is the item that will be "dropped" from the average.
If the window is fixed, we'll be dropping one number and adding one
number every time we move to a new item in the list (once we've
processed n of them, at least).

Before we've processed n of them, we don't want to subtract anything
from the previous sum -- we want the running average. We can accomplish
this by sticking n-1 zeros on the head of the samples, and zipping
*that* with the samples.

I haven't commented this version, but if you understand the last one,
you can figure out what it does. Here's the example Ozgur used:

  *Main> :l moving_average.hs
  [1 of 1] Compiling Main             ( moving_average.hs, interpreted )
  Ok, modules loaded: Main.
  *Main> let samples = [1,2,3,4,5,6,7,8,9,10] :: [Float]
  *Main> moving_average 3 samples
  [1.0,1.5,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0]

(They agree.)

It can do a million items pretty quickly considering we're in ghci:

  *Main> let samples = [1..1000000] :: [Float]
  *Main> :set +s
  *Main> length $ moving_average 10 samples
  1000000
  (1.08 secs, 545400640 bytes)


--------

module Main
where

fst3 :: (a,b,c) -> a
fst3 (x, _, _) = x

moving_average :: (Fractional a) => Int -> [a] -> [a]
moving_average _ [] = []
moving_average n samples
  | n <= 0 = []
  | otherwise =
      map fst3 $ scanl1 average sample_triples
      where
        divisors = map fromIntegral $ [1..n] ++ (repeat n)
        n_agos = (map fromIntegral (replicate (n-1) 0)) ++ samples
        sample_triples = zip3 samples divisors n_agos

        average :: (Fractional b) => (b,b,b) -> (b,b,b) -> (b,b,b)
        average (prev_avg, prev_div, dropme) (sample, divisor, n_ago) =
          (new_avg, divisor, n_ago)
          where
            prev_sum = prev_avg * prev_div
            new_avg = (prev_sum + sample - dropme) / divisor