Why use quicksort over arrays when you can do mergesort over lists and get 1) stable behavior and 2) solution to maximum and k-max problems due to laziness? Do you really need arrays?
And quicksort for arrays in ST monad wouldn't copy anything unnecessary.
Actually, I've seen many claims that some algorithms are inherently mutable. So far none stand close scrutiny.
Matrix operations? You better copy intermediate results, that way you'll be safer and faster (parallel algorithms). Good compilers do that behind the curtain (array privatization).
Sorting? Use maps or lists, that way you won't forget something important.
Graph operations? Immutable (inductive) graphs are slower by a constant multiplier and sometimes are faster than their mutable counterparts (tree-based maps are faster for changes than arrays).
The last one is even more amusing when applied to compiler optimizations (i.e., to non-trivial graph algorithms): http://lambda-the-ultimate.org/node/2443 Pure version is less buggy, faster (!) and allows more optimizations.
Why use quicksort over arrays when you can do mergesort over lists
Sure, you can do merge sort. Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. As well as merging lists, since you have to 'reattach' the second list as the tail of the first list.
And quicksort for arrays in ST monad wouldn't copy anything unnecessary.
You have to copy the data from whatever representation you had to something that lives in a memory block in the ST monad.
Actually, I've seen many claims that some algorithms are inherently mutable. So far none stand close scrutiny.
You have probably never read Okasaki...
The rest of your argument proposes that slow is better because of persistence. First, persistence is often not required, second persistence can also be implemented in a mutable language.
> Sure, you can do merge sort. Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. As well as merging lists, since you have to 'reattach' the second list as the tail of the first list.
It's no problem writing a merge-sort in Haskell that uses O(n log n) time. So who cares what the asymptotics of the individual elements of the algorithm are? (You may care about the actual speed of the whole thing and its parts, though.)
And quicksort for arrays in ST monad wouldn't copy anything unnecessary.
Actually, I've seen many claims that some algorithms are inherently mutable. So far none stand close scrutiny.
Matrix operations? You better copy intermediate results, that way you'll be safer and faster (parallel algorithms). Good compilers do that behind the curtain (array privatization).
Sorting? Use maps or lists, that way you won't forget something important.
Graph operations? Immutable (inductive) graphs are slower by a constant multiplier and sometimes are faster than their mutable counterparts (tree-based maps are faster for changes than arrays).
The last one is even more amusing when applied to compiler optimizations (i.e., to non-trivial graph algorithms): http://lambda-the-ultimate.org/node/2443 Pure version is less buggy, faster (!) and allows more optimizations.