I stumbled upon a 'functional programming interview question' recently; and I came up with a really nice functional programming answer, so feel free to drop the quotes actually.

Question: Given 'n' and a stream of floats, return a stream of the running average of the most recent n elements. If there aren't n elements yet output the average of all the elements available.

I looked at the problem and my first thought was a scanl maintaining the sum, count and the last n elements, with an appropriate update function.

Something like:

`avg :: Int -> [Float] -> [Float]

avg b = map getAvg . tail . scanl f def 

    where 

      getAvg (x, _, _) = x

      def = (0, 0, [])

      f :: (Float, Int, [Float]) -> Float -> (Float, Int, [Float])

      f (_, 0, _) v = (v, 1, [v])

      f (avg, n', x:xs) v | n' == b = (avg - x/n + v/n, n', xs++[v])

                          | otherwise = (avg*n/(n+1) + v/(n+1.0), n'+1, x:xs++[v])

          where 

            n :: Float

            n = fi n'

fi = fromIntegral`

We could improve the update function by tracking the sum and calculating the average at the time of `getAvg`

`avg :: Int -> [Float] -> [Float]

avg b = map getAvg . tail . scanl f def 

    where 

      getAvg (x, n, _) = x/fi n

      def = (0, 0, [])

      f :: (Float, Int, [Float]) -> Float -> (Float, Int, [Float])

      f (_, 0, _) v = (v, 1, [v])

      f (s, n', x:xs) v | n' == b = (s - x + v, n', xs++[v])

                        | otherwise = (s + v, n'+1, x:xs++[v])`

While that's pretty functional what with the scanl but I want to improve it.

The inspiration: `avg(i) = (f(i) - f(i-n))/n(i)`

So what do we need in order to calculate the average at some random point in the stream?

The sum of the last n elements and the min(number of elements, n).

Let f(i) | i < 0 = 0

            | otherwise = sum of all elements upto the ith index.

Sum of the last n elements = f(i) - f(i-n)

In the spirit of Haskell we can combine these quite cleanly:

Sum of the elements: `f(i) = scanl (+) 0 l !! i`

Sum of the elements n elements back: `f(i-n) = replicate n 0 ++ f(i) !! i`

`let lSum = scanl (+) 0 l`

Sum of the last n elements : `f(i) - f(i-n) = zipWith (-) lSum (replicate n 0 ++ lSum) !! i`

Number of elements so far: `n(i) = map (fi . min n) [1..] !! i`

Average: `avg(i) = (f(i) - f(i-n))/n(i)`

Join 'em together:  

f :: Int -> [Float] -> [Float]

f n l = zipWith (/) (zipWith (-) lSum lSum') lLen where lLen = map (fi . min n) [1..] lSum = tail (scanl (+) 0 l) lSum' = replicate n 0 ++ lSum  

fi = fromIntegral 

Bootiful.