Go rant

Andrei Alexandrescu SeeWebsiteForEmail at erdani.org
Tue Dec 22 05:24:41 PST 2009


Daniel de Kok wrote:
> On 2009-12-21 19:13:48 +0100, Andrei Alexandrescu 
> <SeeWebsiteForEmail at erdani.org> said:
>> I disagree. We don't want to educate people to write patently 
>> inefficient code and in poor programming practice.
> 
> I do not mind it, it's ok for explaining a concept clearly.

My point is that there is no "concept" being explained. The concept of 
quicksort is not what the FP classic explains.

> Of course, 
> inadequacies should also be discussed. I'd argue that these are also the 
> thinking steps normally involved in designing a solution to a problem: 
> first try to solve it in the obvious way to understand the problem. 
> Then, make a more performant implementation. Of course, performant also 
> depends on the context. I have written a lot of C++ code that tries to 
> squeeze the last bit of performance out of the machine in a single-core 
> world, but it is also difficult to parallelize. In a parallel world, the 
> 'slower' solution is sometimes better.

I'd agree with the above if complexity was not at stake. That's not an 
optimization.

>> In my mind "elegant" and "at a polynomial blowup in complexity" can't 
>> be reconciled anywhere outside a Turing machine introduction where 
>> everything is equivalent within a polynomial difference in time and 
>> space.
> 
> Elegant in the sense of being able to describe a concept briefly. The 
> in-place quicksort does not do this.

In-place partition is largely what quicksort is about. That concept is 
sorely missing from FP qsort. The fact that you need random access if 
you want to avoid quadratic performance is a much more subtle concept 
that is not only missing from FP qsort - it's hidden.

>> I think that's a roundabout way of saying that functional programming 
>> is unable to express certain algorithms easily or at all.
> 
> ...in pure FP. Of course, another problem is that some algorithms are 
> inherently imperative. For instance, I find calculating the edit 
> distance in a performant manner ugly in functional languages.

So then I guess I can be given a break about FP ueber alles.


Andrei



More information about the Digitalmars-d mailing list