"Reedick, Andrew" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]
| Quicksort in Haskell versus C is amazing:
|
http://www.haskell.org/haskellwiki/Introduction#What.27s_good_about_functional_programming.3F
Sorry, bogus comparison, and not so amazing.
1.The short doubly recursive definition of qsort has nothing to do with
Haskell.
2. The Haskell code refers to an external function 'filter'. The C code
inlines the filter code.
If that is shoved to an external function, we get this 'amazing' (but
untested ;-) C code:
void qsort(int a[], int lo, int hi) {
int l;
if (lo < hi) {
ll = partition(a, lo, hi);
qsort( a, lo, ll-1 );
qsort( a, ll+1, hi );
}
}
The is a fair comparision, and it looks nearly as good as the Haskell code.
This can also be written as a one-liner if one finds such to be more
'amazing'.
The C code does not even need code for the base case. Amazing!
3. The Haskell code makes two scans of the array (one for each filter)
instead of just one and makes a copy of the array (minus the pivot) in two
pieces. instead of none Whether the 'slice' 'xs' makes a copy or is just a
view I don't know. Then it does more allocations and copies to put the
separated pieces back together. The C code does the filtering in place.
Hence no need to concatenate the sorted pieces. Of course that looks more
complex -- because it is -- unless hidden away in the
double-filter-in-place partition function. So Haskell trades textual
terseness for computation space and, probably, time.
Python makes the same trade-off, and I like it and use it for that reason.
One can certainly like Haskell for that reason too, but it is a trade-off.
What would be amazing would be a algorithm that could rewrite the
external-arrays Haskell/Python code to the equivalent of the in-place C
code. Can one even write such an equivalent in Haskell? (If it is purely
functional, then no, though one obviously can in Python.)
For efficiency, standard C qsort code turns the second (tail) recursive
call into a loop. A Python version of the same could easily eliminate the
first recursive call with an explicit stack. Again, less elegant code for
more speed.
| Quicksort in Python inspired by Haskell's quicksort:
| http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/66473
The list slicing could be done once instead of twice.
Terry Jan Reedy
--
http://mail.python.org/mailman/listinfo/python-list
