Posts Tagged ‘average’

Programming Praxis – Sliding Median

June 29, 2012

In today’s Programming Praxis exercise, our goal is to determine the median values of a sliding window over a stream of numbers. Let’s get started, shall we?

A quick import:

import Data.List

Sinze Haskell is lazy by default, we don’t have to do anything special to only load the needed part of the list. We can just use tails and take to generate all the needed windows, after which we sort each window and take either the middle or the average of the middle two values, depending on whether the window contains an even or an odd number of elements.

slidingMedian :: (Ord a, Fractional a) => Int -> Int -> [a] -> [a]
slidingMedian size count =
    map ((\ ~(x:xs) -> if odd size then x else (x + head xs) / 2) .
         drop (div (size - 1) 2) . sort . take size) . take count . tails

A test to see if everything is working properly:

main :: IO ()
main = mapM_ print $ slidingMedian 5 12
    [13, 28, 94, 34, 32, 78, 12, 10, 84, 93, 45, 66, 67, 52, 24, 49]