[Haskell-cafe] k-minima in Haskell

Stefan O'Rear stefanor at cox.net
Wed Apr 11 23:38:48 EDT 2007


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


More information about the Haskell-Cafe mailing list