A few comments on this (stuff after the line beneath):
The C implementation isn't really that inefficient. A factor of log(n)
in average of course a factor of n i worst case.
This doesn't change when using a lazy language! because of the nature of
quicksort.
As a matter of fact you have to have a "nice" version of merge sort
(there are several
variants - see fx Ralf Hinze, A Data-structural Look at Sorting, 1998, I
don't know if it has been published except on this list) to be sure that
(hd (sort list)) runs in time O(n).
But, you are right a degree in CS doesn't guarantee that you know about
complexity,
but neither does programming in a lazy language. Personally I'm
programming large
systems in Prolog (www.pdc.dk) upto 150K lines. We try to make programs
readable and
correct firstmost, when they are too slow we measure where and fix it.
Carsten Kehler Holst
------------------------------------------------------------------------
------------
Fergus wrote:
> I guess one could argue that the costs of most other things pale
> in comparison to the costs of having lazy evaluation as the default
;-)
Of course, if you're the sort of person who likes to write "head (sort
lst)"
to get the least member of a list, then lazy evaluation is incredibly
efficient. Getting used to lazy evaluation, and really learning how to
use
it properly, is probably really the hardest thing about Haskell for
someone
who has already learned how to program using strict languages. Possibly
even
harder than monads.
Funny/sad anecdote: I once saw a senior software engineer with over 15
years
of C experience and a master's degree in CS, write the following code in
C
to locate the least member of an array:
qsort(array,
sizeof(array) / sizeof(array[0]),
sizeof(array[0]),
comparator);
least = array[0];
Essentially, this is just "head (sort lst)" in C, which, as I daresay we
all
know, is NOT a lazy language! I actually had to explain to her why it
was
inefficient. Depending how you look at it, this is either strong
evidence
that lazy evaluation is a more natural way to think than strict
evaluation,
or proof that a master's in CS doesn't necessarily mean you really know
anything about programming.
Craig
