CODEWITHSUNDEEP
arrayshaskellmoving-averageweighted-average
Uri Goren
Uri Goren

Reputation: 13690

Moving average in Haskell

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.

Upvotes: 4

Views: 609

Answers (3)

Julia Path
Julia Path

Reputation: 2366

tails gives you a list of the tails of the input list. So tails [1,2,3] = [[1,2,3],[2,3],[3],[]]. Since we don't need the last empty list we use (init.tails) to get everything in the tails list except the last element.

import Data.List (tails)
averages :: Num a => [a] -> [a] -> [a]
averages weights xs = sum . zipWith (*) weights <$> (init.tails) xs

Note that this very likely doesn't behave the way you want at the start and end of the list. Especially because it behaves different at the start then at the end. The first element will be the average of the first length weight element, but the last element will only be head weight * last xs.

If you want the behaviour of the end at the start you can use something like this:

import Data.List (tails)
averages :: Num a => [a] -> [a] -> [a]
averages weights xs = sum . zipWith (*) weights <$>
  (init.tails) (replicate (length weights - 1) 0 ++ xs)

If you want the behaviour of the end at the start you can use this:

import Data.List (tails)
averages :: Num a => [a] -> [a] -> [a]
averages weights xs = sum . zipWith (*) weights <$>
  takeWhile (not . null . drop (l-1)) (tails xs)
  where l = length weights

If you want to start and end with the first/last element being multiplied with the center element of the weights list we have to use a combination of the two above answers:

import Data.List (tails)
averages :: Num a => [a] -> [a] -> [a]
averages weights xs = sum . zipWith (*) weights <$>
  takeWhile (not . null . drop half) (replicate half 0 ++ xs)
  where half = length weights `quot` 2

Upvotes: 2

Will Ness
Will Ness

Reputation: 71075

The zipping takes care of the alignment automagically:

wma :: Num a => [a] -> [a] -> [a]
wma weights = map (sum . zipWith (*) weights )   -- weighted-moving-average
                . foldr (zipWith (:)) (repeat []) 
                . take (length weights) 
                . tails

(see also).

Upvotes: 3

phadej
phadej

Reputation: 12123

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!

Upvotes: 4

Related Questions