3 ms·
> The Haskell quicksort is the classic example of this: The Haskell quicksort is also classic example of something that is small, beautiful and still misses th
by seppel 6y ago
> The Haskell quicksort is the classic example of this:
The Haskell quicksort is also classic example of something that is small, beautiful and still misses the point. Yes, it contains the core idea of quicksort (partion the list and divide and conquer) but it completely fails on the quick part, because the Haskell lists are are leaky abstraction of real computer memory.
A real quicksort in Haskell is much more convoluted.
- hashingroll 6y agoWhat's a real quicksort anyway? You could argue that a reasonably fast implementation of quicksort is much more convoluted, which it most certainly is, but that doesn't make this implementation any less real.
- seppel 6y ago> What's a real quicksort anyway? A key aspect of quicksort is that it sorts the list in-place. If you dont sort in-place, you dont have quicksort and if you dont need in-place sort, then quicksort is the wrong choice anyway. Of course, canonical Haskell does not have a concept of in-place, which makes showing quicksort in Haskell also a questionable idea. > You could argue that a reasonably fast implementation of quicksort is much more convoluted, which it most certainly is, but that doesn't make this implementation any less real. A reasonably fast implementation of quicksort is straight-forward in any language that has arrays/vectors with destructive updates. This implementation will have issues with pathological cases, but that's a problem of the quicksort algorithm, not of the implementation (whereas the Haskell one shown above has problems in the implementation).
- n4r9 6y agoSounds like a hardware issue.
- oblio 6y agoWhich hardware does not have this issue?