There seems to be some confusion about the question. There are two key things to keep in mind here:
1) You must make at most O(k*n) comparisons (in the worst case) if the list has length n.
2) The output must be the indices and not the numbers themselves.
So, any algorithm that sorts is no good (think of n as huge, and k small). Another interesting caveat to this is that if k=2, you can actually solve the problem with just (n+log n) comparisons in worst case(instead of 2*n, that you get by a naive approach), and it's a nice exercise to do this.
As a further clarification, this is not a homework question. I genereally do whatever programming I do in Matlab, as I work with matrices (huge ones) and use this function a lot. I just wanted to see how different an implementation you can get in Haskell (I am new to Haskell so I might not be able to come up with the best way to do this).
----- Original Message ----
From: Stefan O'Rear
On Thu, Apr 12, 2007 at 08:58:33AM +0530, raghu vardhan wrote:
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.
Go read and thoroughly understand "Why Functional Programming Matters."
Also, your asyptotic complexity bound is just plain wrong. I'd give faster code, but Don is suspicious (and I can never tell these things myself).
Stefan
Don tells me (in #haskell) that you are legitimate, so here is the
example:
kminima k lst = take k $ sort lst
If you want to be really explicit about it, here is a sort that will
work:
sort [] = []
sort l@(x:_) = filter (