9 ms·

> The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort

by dualogy 10y ago

> The prime example of this is the Haskell "Quicksort" implementation, which is, of course, not actually quick and only vaguely related to the idea of Quicksort. Yeah but at least it's lazy! ;) If you only ask to (sort) because from the result you're going to (take) the say 4 (smallest/latest/whatever-est), it'll only just sort-enough to give you these 4 sorted, unneeded values being discarded (usually) partially unsorted --- no matter the size of the total. (Still, there may no doubt well be better quicksorts for Haskell out there..) Of course you can write this sort of specific short-cutting in any language manually, but with lazy-evaluation it's just the standard behaviour for any naive `(take 4 (sortBy mysorter mydata))`-type expression. (Takeaway regarding "quick" above: everything regarding performance and efficiency in lazily-evaluated pure functional languages depends to a large degree on the current live data; predictability gets harder here consequently.)

mpweiher 10y ago
> Yeah but at least it's lazy! ;) ;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerly. > just sort-enough to give you these 4 sorted And how is that going to work in a sort? The 4 first elements can be located anywhere and have to brought into position. There are "first k of n" algorithms, but these are (last I checked) quite different from generic sorting algorithms, and I doubt that a lazy sort in Haskell actually magically turns into one of those algorithms. Happy to be proved wrong!
- fmap 10y ago
  Well, you do get an (expected time) asymptotically efficient algorithm for sorting the first k elements of an array by running quicksort without recursing on the last n-k elements. This is what you get in Haskell with "take k (sort xs)". But, as you mentioned the constant factors involved are ridiculously high and this is not going to give you a practical solution.

by dualogy 10y ago

mpweiher 10y ago

> Yeah but at least it's lazy! ;) ;) Yeah, except that the overhead of lazy is often (usually?) more than the "overhead" of doing the whole computation eagerly. > just sort-enough to give you these 4 sorted And how is that going to work in a sort? The 4 first elements can be located anywhere and have to brought into position. There are "first k of n" algorithms, but these are (last I checked) quite different from generic sorting algorithms, and I doubt that a lazy sort in Haskell actually magically turns into one of those algorithms. Happy to be proved wrong!

fmap 10y ago
Well, you do get an (expected time) asymptotically efficient algorithm for sorting the first k elements of an array by running quicksort without recursing on the last n-k elements. This is what you get in Haskell with "take k (sort xs)". But, as you mentioned the constant factors involved are ridiculously high and this is not going to give you a practical solution.