4 ms·

> It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. Do you know of one? All the fast array-based quicksorts I ha

by Athas 10y ago

> It's also mostly straightforward to implement a fast Quicksort using mutable arrays in Haskell. Do you know of one? All the fast array-based quicksorts I have seen in Haskell have been very awkward compared to implementations in imperative languages with good array support (and they have been quite slow as well). I don't feel like this is much of an indictment against Haskell. Sure, a functional language isn't a good fit for a very imperative algorithm, but that's not really its target domain.

codygman 10y ago
http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html http://www.haskellforall.com/2013/05/program-imperatively-us...
- Athas 10y ago
  I can't find a quicksort implementation on the other side of that link.
  - codygman 10y ago
    Sorry, I meant to say you could pretty easily make quicksort using the techniques in that link.
harpocrates 10y ago
I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but every line has a very clear purpose. Most implementations on Rosetta code in other languages [2] seem to be about as long. [1] https://gist.github.com/harpocrates/bbed7b6837d524aafa02 https://gist.github.com/harpocrates/bbed7b6837d524aafa02 [2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort https://rosettacode.org/wiki/Sorting_algorithms/Quicksort
- Athas 10y ago
  Thank you, that is a very nice implementation! I think the key is that the vector library is very well designed - it has certainly been the cause of the majority of my Haskell performance successes. I'll say that your implementation benefits from being able to access partitioning as a library function - the actual implementation of unstablePartition is not particularly pretty (but it is conceptually simple).

by Athas 10y ago

codygman 10y ago

http://www.haskellforall.com/2013/05/program-imperatively-using-haskell.html http://www.haskellforall.com/2013/05/program-imperatively-us...

Athas 10y ago
I can't find a quicksort implementation on the other side of that link.
- codygman 10y ago
  Sorry, I meant to say you could pretty easily make quicksort using the techniques in that link.

harpocrates 10y ago

I wrote a pretty concise version of it a while ago to convince myself it was possible [1]. It isn't as short as the naive (incorrect) quicksort using lists, but every line has a very clear purpose. Most implementations on Rosetta code in other languages [2] seem to be about as long. [1] https://gist.github.com/harpocrates/bbed7b6837d524aafa02 https://gist.github.com/harpocrates/bbed7b6837d524aafa02 [2] https://rosettacode.org/wiki/Sorting_algorithms/Quicksort https://rosettacode.org/wiki/Sorting_algorithms/Quicksort

Athas 10y ago
Thank you, that is a very nice implementation! I think the key is that the vector library is very well designed - it has certainly been the cause of the majority of my Haskell performance successes. I'll say that your implementation benefits from being able to access partitioning as a library function - the actual implementation of unstablePartition is not particularly pretty (but it is conceptually simple).