The link pretty much answers my question, though you probably require a little bit more book keeping to get the indices out. Compared to the iterative version or the matlab version, this definitely is more elegant, but also is trickier.
apfelmus wrote: > > raghu vardhan <[EMAIL PROTECTED]>: >> 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 > > > [EMAIL PROTECTED] 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 > > _______________________________________________ > Haskell-Cafe mailing list > [EMAIL PROTECTED] > http://www.haskell.org/mailman/listinfo/haskell-cafe > > -- View this message in context: http://www.nabble.com/k-minima-in-Haskell-tf3563220.html#a9964572 Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com. _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe