[Haskell-cafe] k-minima in Haskell
ajb at spamcop.net
ajb at spamcop.net
Thu Apr 12 01:33:50 EDT 2007
G'day all.
Quoting raghu vardhan <mrvr84 at yahoo.co.in>:
> What's the best way to implement the following function in haskell:
> Given a list and an integer k as input return the indices of the least k
> elements in the list. The code should be elegant and also, more importantly,
> must not make more than the minimum O(k*length(list)) number of operations.
Pretty much like everyone has says, although it's best to use a real
lazy O(n log n) sort, not quicksort-with-dumbest-pivot. To get the
indices, use the Schwartzian transform:
sortWith :: (Ord b) => (a -> b) -> [a] -> [a]
sortWith f = mergeRuns . runs
where
runs = map (:[])
mergeRuns [] = []
mergeRuns [xs] = xs
mergeRuns xss = mergeRuns (mergeRun xss)
mergeRun (xs1:xs2:xss) = mergeOne xs1 xs2 : mergeRun xss
mergeRun xss = xss
mergeOne [] ys = ys
mergeOne xs [] = xs
mergeOne xs'@(x:xs) ys':(y:ys)
= case compare (f x) (f y) of
LT -> x : mergeOne xs ys'
GT -> y : mergeOne xs' ys
EQ -> x : y : mergeOne xs ys
getKMinima :: (Ord a) => [a] -> [Int]
getKMinima k = map fst . take k . sortWith snd . zip [0..]
Cheers,
Andrew Bromage
More information about the Haskell-Cafe
mailing list