Last active
August 29, 2015 14:05
-
-
Save fishcorn/1a5bde88ecde525b221a to your computer and use it in GitHub Desktop.
Utils.hs
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
-- | 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 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment