CODEWITHSUNDEEP
haskell
Xie
Xie

Reputation: 627

Haskell: A function to compute the median value of a list

I have written a function to compute the median value of a list

task3 xs  | null xs  = Nothing
          | odd  len = xs !! mid
          | even len = evenMedian
                where  len = length xs
                       mid = len `div` 2
                       evenMedian = (xs !! mid + xs !! (mid+1)) / 2

I thought it is right and it also pass the load. But when I use the function, it did not work. What is wrong here?

Upvotes: 1

Views: 7947

Answers (5)

Agnishom Chattopadhyay
Agnishom Chattopadhyay

Reputation: 2041

How about Median of Medians? Note that this computes only an approximation to the median.

Here is a Haskell implementation:

import Data.List

median :: Ord a => [a] -> a
median xs = select (length xs `div` 2) xs

select :: Ord a => Int -> [a] -> a
select i xs
  | n <= 5
  = sort xs !! i
  | lengthLower == i
  = medianOfMedians
  | lengthLower < i
  = select (i - lengthLower - 1) upperPartition
  | otherwise
  = select i lowerPartition
  where
    n = length xs
    medianOfMedians = median (map median (chunksOf 5 xs))
    (lowerPartition, _:upperPartition) = partition (< medianOfMedians) xs
    lengthLower = length lowerPartition

chunksOf :: Int -> [a] -> [[a]]
chunksOf _ [] = []
chunksOf n xs
  | (beginning, rest) <- splitAt n xs
  = beginning : chunksOf n rest

Upvotes: 3

christian wuensche
christian wuensche

Reputation: 1043

My version of median for Integer

import Data.List (sort)

getMiddle [] = 0
getMiddle xs = (a' + b') `div` 2
    where a' = head $ drop a xs
          b' = head $ drop b xs
          a = (n `div` 2)
          b = n' - 1
          n' = n `div` 2
          n = length xs

median :: [Integer] -> Integer
median [] = 0
median xs = result
    where result = if (n `mod` 2 == 0)
                    then getMiddle sorted
                    else head $ drop a sorted
          a = (n - 1) `div` 2
          n = length xs
          sorted = sort xs


main = print $ median [1, 4, 5, 7, 9, 100]
-- 6

Upvotes: 1

bas080
bas080

Reputation: 469

Recursion could do the job also.

import Data.List

medianFromSorted :: Fractional a => [a] -> Maybe a
medianFromSorted [] = Nothing
medianFromSorted [a] = Just a
medianFromSorted [a,b] = Just ((a + b) / 2)
medianFromSorted (a:xs) = medianFromSorted (init xs) -- init is not efficient

median :: Ord a => Fractional a => [a] -> Maybe a
median = medianFromSorted . sort

Upvotes: 1

user1104160
user1104160

Reputation: 305

Even with kaan's answer, this code will still not produce a correct median. Another issue that has been overlooked is that Haskell lists are zero indexed. As a result, all of the code is correct with kaan's additions except

evenMedian = (xs !! mid + xs !! (mid+1)) / 2

which should actually be

evenMedian = (xs !! (mid - 1) + xs !! mid) / 2

Otherwise the result is incorrect. The wrong way produces task3 [1, 2, 3, 4] == Just 3.5, while the correct way produces task3 [1, 2, 3, 4] == Just 2.5

Upvotes: 0

kaan
kaan

Reputation: 796

As Lee mentioned, the list must be sorted first. (The median of [1,1,8,1,1] is 1 (not 8). so you have to sort it to [1,1,1,1,8] and then take the one in the middle).

The other thing is, that you return Nothing, so the other results have to be of type Maybe a too: Just $ xs !! mid

Just evenMedian

You can use sort from Data.List to sort your list before applying it to task3. Like so:

task xs = task3 (sort xs)

Upvotes: 4

Related Questions