Programming Praxis – Sliding Median

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]
About these ads

Tags: , , , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: