[Haskell-cafe] Re: k-minima in Haskell

[apfelmus]

raghu vardhan <mrvr84 at yahoo.co.in>:
> So, any algorithm that sorts is no good (think of n as huge, and k small).

With lazy evaluation, it is!

  http://article.gmane.org/gmane.comp.lang.haskell.general/15010


ajb at spamcop.net wrote:
> The essence of all the answers that you've received is that it doesn't
> matter if k is small, sorting is still the most elegant answer in Haskell.

(It's not only most elegant, it can even be put to work.)

> The reason is that in Haskell, a function which sort function will produce the
> sorted list lazily. If you don't demand the while list, you don't perform
> the whole sort.
> 
> Some algorithms are better than others for minimising the amount of
> work if not all of the list is demanded, but ideally, producing the
> first k elements will take O(n log k + k) time.

You mean O(k * log n + n) of course.

Regards,
apfelmus