Moving average in Haskell

Question

Given a list of weights:

let weights = [0.1, 0.2, 0.4, 0.2, 0.1]

and an array of measurements, I want to implement the weighted average.

This is how I would do it in Python:

y=[]
w = length(weights)
for n in range(w,len(x)-w):
    y[n-w/2-1]=sum([a*b for a,b in zip(weights,x[n-w/2:n+w/2+1])])
    #y[n-3]=W[1]*x[n-2]+W[2]*x[n-1]+W[3]*x[n]+W[4]*x[n+1]+W[5]*x[n+2]

I know Haskell doesn't have arrays, what I'm trying to achieve is a low-pass-filter, in which I can define the weights manually.

Answer 1

Moving average can be calculated with a mealy machine, where the internal state is previous values.

I'll show a moving average over three arguments example, you can fiddle yourself to e.g. make it parametrisable in size.

Mealy machine is essentially an initial state, and "state + input" to "new state + output" function:

Mealy i o ~ (s, s -> i -> (o, s))

Let's assume that initial state is all zeros, and write a function for moving average over 3.

type S = (Double, Double)
type I = Double
type O = Double

initialState :: S
initialState = (0, 0)

weight0, weight1, weight2 :: Double
weight0 = 0.25
weight1 = 0.5
weight2 = 0.25

ma :: S -> I -> (O, S)
ma (x0, x1) x2 = (o, s)
    where
    s = (x1, x2)
    o = x0 * weight0 + x1 * weight1 + x2 * weight2

Now we got all the pieces, let's run the machine on the input:

runMealy :: (S -> I -> (O, S)) -> S -> [I] -> [O]
runMealy _ _ [] = []
runMealy f s (x : xs) =
    let (o, s') = f s x
    in o : runMealy f s' xs

And try it:

λ *Main > runMealy ma initialState [1,2,3,4,5,6,7,8,9]
[0.25,1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0]

---

You can drop first produced values, as machine internal state is "warming up".

---

For arbitrary sized moving average machine, you could use Data.Sequence, as it's much better data structure when you push to one end, while pop from another, then single linked list, [].

---

Why I'm talking about Mealy machine? Because at some point you'll most likely run into situation where you need to use some streaming library in Haskell: pipes, conduit or machines. Then Mealy machine approach will be the only reasonable solution.

Also you can make autoregressive models as well!