Computing Moving Average in Haskell

Question

I'm working on learning Haskell, so I tried to implement a moving average function. Here is my code:

mAverage :: Int-> [Int] -> [Float]
mAverage x a = [fromIntegral k / fromIntegral x | k <- rawAverage]
    where
    rawAverage = mAverage' x a a

-- First list contains original values; second list contains moving average computations
mAverage' :: Int -> [Int] -> [Int] -> [Int]
mAverage' 1 a b = b
mAverage' x a b = mAverage' (x - 1) a' b'
    where
    a' = init a
    b' = zipWith (+) a' (tail b)

where the user calls mAverage with a length for each average and the list of values (e.g. mAverage 4 [1,2..100]).

However, when I run the code on the input mAverage 4 [1,2..100000], I get that it takes 3.6 seconds in ghci (using :set +s) and uses a gigabyte of memory. This seems very inefficient to me, as the equivalent function takes a fraction of a second in Python. Is there some way that I could make my code more efficient?

Answer 1

If you want to learn something new you can take a look at this nice solution for Moving Average problem. It is written by one of my students so I won't claim authorship. I really like it because it's very short. The only problem here is average function. Such functions are known to be bad. Instead you can use Beautiful folds by Gabriel Gonzalez. And yes, this function takes O(k) time (where k is size of window) for calculating average of window (I find it better because you can face floating point errors if you try to add only new element to window and subtract last). Oh, it also uses State monad :)

{-# LANGUAGE UnicodeSyntax #-}

module MovingAverage where

import           Control.Monad       (forM)
import           Control.Monad.State (evalState, gets, modify)

moving :: Fractional a ⇒ Int → [a] → [a]
moving n _  | n <= 0 = error "non-positive argument"
moving n xs = evalState (forM xs $ \x → modify ((x:) . take (n-1)) >> gets average) []
  where
    average xs = sum xs / fromIntegral n