Posts Tagged ‘median’

Programming Praxis – Median Of Five

December 4, 2012

In today’s Programming Praxis exercise, our goal is to determine to median of five numbers using only six comparisons. Let’s get started, shall we?

A quick import:

import Data.List

I didn’t like the element swapping and nested ifs of the provided algorithm, so I tried to come up with something a litte more in the spirit of functional programming. I was initially worried that the case statement would evaluate all three comparisons when the the first one was false, but some testing revealed that Haskell is lazy enough to skip the second comparison in that case.

median5 :: Ord a => [a] -> a
median5 ~[a',b',c,d',e'] = case (b<c, b<d, d<c) of
        (True, True , _    ) -> min c d
        (True, False, _    ) -> min b e
        (False, _   , True ) -> min c e
        (False, _   , False) -> min b d
    where ((_,b), (d,e)) = order (order a' b') (order d' e')
          order x y = if y < x then (y,x) else (x,y)

All that’s left to do is to verify that all permutations of the numbers 1 to 5 result in 3 as the median.

main :: IO ()
main = print . all ((== 3) . median5) $ permutations [1..5]

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]