module Median ( median ) where import Control.Monad.Primitive (PrimMonad, PrimState) import qualified Data.Vector.Algorithms.Merge as Merge import Data.Vector.Generic.Mutable (MVector) import qualified Data.Vector.Generic.Mutable as MV median :: (PrimMonad m, MVector v e, Ord e, Fractional e) => v (PrimState m) e -> m e median :: forall (m :: * -> *) (v :: * -> * -> *) e. (PrimMonad m, MVector v e, Ord e, Fractional e) => v (PrimState m) e -> m e median v (PrimState m) e v = do v (PrimState m) e -> m () forall (m :: * -> *) (v :: * -> * -> *) e. (PrimMonad m, MVector v e, Ord e) => v (PrimState m) e -> m () Merge.sort v (PrimState m) e v let l :: Int l = v (PrimState m) e -> Int forall (v :: * -> * -> *) a s. MVector v a => v s a -> Int MV.length v (PrimState m) e v if Int -> Bool forall a. Integral a => a -> Bool odd Int l then v (PrimState m) e v v (PrimState m) e -> Int -> m e forall (m :: * -> *) (v :: * -> * -> *) a. (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a `MV.read` ((Int l Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1) Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 2) else do e x0 <- v (PrimState m) e v v (PrimState m) e -> Int -> m e forall (m :: * -> *) (v :: * -> * -> *) a. (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a `MV.read` ((Int l Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 2) Int -> Int -> Int forall a. Num a => a -> a -> a - Int 1) e x1 <- v (PrimState m) e v v (PrimState m) e -> Int -> m e forall (m :: * -> *) (v :: * -> * -> *) a. (PrimMonad m, MVector v a) => v (PrimState m) a -> Int -> m a `MV.read` (Int l Int -> Int -> Int forall a. Integral a => a -> a -> a `div` Int 2) e -> m e forall (f :: * -> *) a. Applicative f => a -> f a pure (e -> m e) -> e -> m e forall a b. (a -> b) -> a -> b $ (e x0 e -> e -> e forall a. Num a => a -> a -> a + e x1) e -> e -> e forall a. Fractional a => a -> a -> a / e 2