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.)
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.