[Haskell-cafe] k-minima in Haskell

[ajb at spamcop.net]

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