Comment by simiones
16 days ago
Well, I'd say using an entirely different collection type than the rest of language (STArray instead of [a]) is already a big complication. It also ends up being more than double the size of the Java code. And, as the author admits, it's actually even slower than the original not-quicksort implementation above, because it actually has to make a copy of the original list, and then return a copy of the mutated array.
So, one of the best sorting algorithms ever devised is not actually usable to sort a [a] in Haskell... I maintain this is a good example of making an easy problem tough.
> I'd say using an entirely different collection type than the rest of language (STArray instead of [a]) is already a big complication
Haskell uses many different collection types, just like any other language. Why not?
> it's actually even slower than the original not-quicksort implementation above, because it actually has to make a copy of the original list, and then return a copy of the mutated array.
Sure, but it could also not do that, if callers are happy to provide a mutable array, just like any other language ...
> one of the best sorting algorithms ever devised is not actually usable to sort a [a] in Haskell
Indeed! One of the best algorithms for sorting a mutable array can't be used on an immutable data type, just like any other language ...
None of this invalidates your original claim that "It's significantly easier in C than it is in Haskell" of course.
quicksort2 has a very reasonable constraint of Array, it's the helpers that use the STArray implementation. I suspect it wouldn't be hard to port to MArray, though I don't know that it would perform any better (maybe avoiding some copies since MArray is actually usable outside of runST). I also suspect the overhead of the copies pays off with larger lists given the lack of space leaks compared to the naive algorithm. Some benchmarks of different-sized lists would have been nice.
I'm not a cheerleader for Haskell, it's not the most appropriate language for every job (certainly not for quicksort). But some folks suddenly become hyper-optimizing assembly programmers whenever anyone has the thought of porting a sql crud app to another language... Horses for courses and all that.