G'day all.
Quoting raghu vardhan
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