-----------------------------------------------------------------------------
-- |
-- Module      :  Numeric.Statistics.Median
-- Copyright   :  (c) Matthew Donadio 2002
-- License     :  GPL
--
-- Maintainer  :  m.p.donadio@ieee.org
-- Stability   :  experimental
-- Portability :  portable
--
-- Simple module for computing the median on a list
--
-- Reference: Ross, NRiC
--
-----------------------------------------------------------------------------

module Numeric.Statistics.Median (median, medianFast) where

import Data.List (sort)

-- | Compute the median of a list

median :: (Ord a, Fractional a) => [a] -> a
median :: forall a. (Ord a, Fractional a) => [a] -> a
median [a]
x =
   if forall a. Integral a => a -> Bool
odd Int
n
     then forall a. Ord a => [a] -> [a]
sort [a]
x forall a. [a] -> Int -> a
!! (Int
n forall a. Integral a => a -> a -> a
`div` Int
2)
     else ((forall a. Ord a => [a] -> [a]
sort [a]
x forall a. [a] -> Int -> a
!! (Int
n forall a. Integral a => a -> a -> a
`div` Int
2 forall a. Num a => a -> a -> a
- Int
1)) forall a. Num a => a -> a -> a
+ (forall a. Ord a => [a] -> [a]
sort [a]
x forall a. [a] -> Int -> a
!! (Int
n forall a. Integral a => a -> a -> a
`div` Int
2))) forall a. Fractional a => a -> a -> a
/ a
2
    where n :: Int
n = forall (t :: * -> *) a. Foldable t => t a -> Int
length [a]
x


{- |
Compute the center of the list in a more lazy manner
and thus halves memory requirement.
-}

medianFast :: (Ord a, Fractional a) => [a] -> a
medianFast :: forall a. (Ord a, Fractional a) => [a] -> a
medianFast [] = forall a. HasCallStack => [Char] -> a
error [Char]
"medianFast: empty list has no median"
medianFast [a]
zs =
   let recurse :: [a] -> [a] -> a
recurse (a
x0:[a]
_)    (a
_:[])   = a
x0
       recurse (a
x0:a
x1:[a]
_) (a
_:a
_:[]) = (a
x0forall a. Num a => a -> a -> a
+a
x1)forall a. Fractional a => a -> a -> a
/a
2
       recurse (a
_:[a]
xs)    (a
_:a
_:[a]
ys) = [a] -> [a] -> a
recurse [a]
xs [a]
ys
       recurse [a]
_ [a]
_  =
          forall a. HasCallStack => [Char] -> a
error [Char]
"median: this error cannot occur in the way 'recurse' is called"
   in  forall {a} {a}. Fractional a => [a] -> [a] -> a
recurse [a]
zs [a]
zs