Utils.hs

gistfile1.hs

-- | Find the element which has @n@ other elements less than or equal
-- to it from the input.
--
-- NB: works best for unordered inputs. Pivots on the first element,
-- so is worst-case quadratic.
nthRank :: (Ord a) => Int -> [a] -> Maybe a
nthRank _ []     = Nothing
nthRank 0 xs     = Just $ minimum xs
nthRank n xs'@(x:xs)
  | n < 0                      = Nothing
  | and $ zipWith (<=) xs' xs  = listToMaybe . drop n $ xs' -- non-descending list 
  | n == m                     = Just x                     -- found
  | n < m                      = nthRank n low              -- in the low side 
  | otherwise                  = nthRank (n-m-1) high       -- in the high side
  where (low, high) = partition (<= x) xs
        m           = length low