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
```