What Programming Languages Should You Learn Next?

Terry Reedy tjreedy at udel.edu
Fri Mar 21 03:29:05 CET 2008


"Reedick, Andrew" <jr9445 at ATT.COM> wrote in message 
news:A20311AF91C11640ACBB721DC2558B4907D2F5A7 at brexc51p...
| 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 






More information about the Python-list mailing list