module Numeric.Statistics.Median (median, medianFast) where
import Data.List (sort)
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
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