[Haskell-cafe] k-minima in Haskell

[Stefan O'Rear]

On Wed, Apr 11, 2007 at 08:38:48PM -0700, Stefan O'Rear wrote:
> 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 (<x) l ++ filter (==x) l ++ filter (>x) l

(A stable quicksort, btw)

Note that this is FASTER than your bound - somewhere between O(n) and
O(n*log n).

Ain't lazy evaluation great? :)

Stefan