3 ms·

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, whi

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.

eru 15y ago
I agree with you in most cases. > 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.)
thesz 15y ago
>Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. Oh, no. You shouldn't split list by calculating length. Try this instead: even (x:_:xs) = x : even xs even xs = xs odd = even . drop 1 splitList xs = (even xs, odd xs) Voila! Completely lazy, O(1). So for merge. See here: http://lambda-the-ultimate.org/node/608?from=0&comments_per_page=200 http://lambda-the-ultimate.org/node/608?from=0&comments_... The solution contains proper merge algorithm. And yes, I never read Okasaki in full. But, I use Haskell semi-professionally from 1999 and professionally from 2006.

eru 15y ago

I agree with you in most cases. > 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.)

thesz 15y ago

>Except that the list split step in Haskell is O(n) in time, while it is constant when using arrays. Oh, no. You shouldn't split list by calculating length. Try this instead: even (x:_:xs) = x : even xs even xs = xs odd = even . drop 1 splitList xs = (even xs, odd xs) Voila! Completely lazy, O(1). So for merge. See here: http://lambda-the-ultimate.org/node/608?from=0&comments_per_page=200 http://lambda-the-ultimate.org/node/608?from=0&comments_... The solution contains proper merge algorithm. And yes, I never read Okasaki in full. But, I use Haskell semi-professionally from 1999 and professionally from 2006.