On 26/08/13 01:06, Andrei Alexandrescu wrote:
> This is one of the worst PR functional programming has ever gotten, and one of
> the worst things FP has done to the larger community. Somebody should do hard
> time for this. And yes, for that matter it's a great example in which SLOCs are
> not a very good measure.

I thought you'd like me bringing this up. ;-)

On Sunday, 25 August 2013 at 23:16:17 UTC, Joseph Rushton Wakeling wrote:
> On 26/08/13 01:06, Andrei Alexandrescu wrote:
>> This is one of the worst PR functional programming has ever gotten, and one of
>> the worst things FP has done to the larger community. Somebody should do hard
>> time for this. And yes, for that matter it's a great example in which SLOCs are
>> not a very good measure.
>
> I thought you'd like me bringing this up. ;-)

You still have a chance, because I don't quite get it. With the little I know about Haskell, I find this code very elegant. What is wrong with it? Performance?

Paul Jurczak:

> You still have a chance, because I don't quite get it. With the little I know about Haskell, I find this code very elegant. What is wrong with it? Performance?

A faithful QuickShort should work in-place, unlike that code.

This is an implementation of a similar functional algorithm in D, a "fake" QuickSort:


import std.stdio, std.algorithm, std.range, std.array;

auto quickSort(T)(T[] items) /*pure*/ nothrow {
    if (items.length < 2)
        return items;
    auto pivot = items[0];
    return items[1 .. $].filter!(x => x < pivot).array.quickSort ~
           pivot ~
           items[1 .. $].filter!(x => x >= pivot).array.quickSort;
}

void main() {
    [4, 65, 2, -31, 0, 99, 2, 83, 782, 1].quickSort.writeln;
}



It's a similar situation with the Sieve of Eratosthenes. There are ways to write an acceptable (but a little slower) Sieve of E. with immutable lists, but many of the functional little implementations you see around are not a true Sieve of E.:
http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf

Bye,
bearophile

On Monday, 26 August 2013 at 01:16:21 UTC, Paul Jurczak wrote:
> You still have a chance, because I don't quite get it. With the little I know about Haskell, I find this code very elegant. What is wrong with it? Performance?

It's a huge blowup in time complexity. They say that Lisp programmers know the value of everything and the cost of nothing... That's probably true of Haskell programmers as well.

On Monday, 26 August 2013 at 01:16:21 UTC, Paul Jurczak wrote:
> On Sunday, 25 August 2013 at 23:16:17 UTC, Joseph Rushton Wakeling wrote:
>> On 26/08/13 01:06, Andrei Alexandrescu wrote:
>>> This is one of the worst PR functional programming has ever gotten, and one of
>>> the worst things FP has done to the larger community. Somebody should do hard
>>> time for this. And yes, for that matter it's a great example in which SLOCs are
>>> not a very good measure.
>>
>> I thought you'd like me bringing this up. ;-)
>
> You still have a chance, because I don't quite get it. With the little I know about Haskell, I find this code very elegant. What is wrong with it? Performance?

It is a quick copy copy copy no so quick sort.

On 8/25/13 6:16 PM, Paul Jurczak wrote:
> On Sunday, 25 August 2013 at 23:16:17 UTC, Joseph Rushton Wakeling wrote:
>> On 26/08/13 01:06, Andrei Alexandrescu wrote:
>>> This is one of the worst PR functional programming has ever gotten,
>>> and one of
>>> the worst things FP has done to the larger community. Somebody should
>>> do hard
>>> time for this. And yes, for that matter it's a great example in which
>>> SLOCs are
>>> not a very good measure.
>>
>> I thought you'd like me bringing this up. ;-)
>
> You still have a chance, because I don't quite get it. With the little I
> know about Haskell, I find this code very elegant. What is wrong with
> it? Performance?

I ranted about that a couple of times (including during my DConf talk). In brief:

1. quicksort is based on in-place partition, so at best that example is a different (and less adequate) algorithm inspired from quicksort.

2. choosing the first element as pivot yields quadratic performance on almost sorted sequence, which is a common practical case.

That example is part of a toxic trifecta (also including the doubly-exponential fibonacci and the O(N) space factorial) that has done a lot of bad teaching.


Andrei

On Monday, 26 August 2013 at 03:44:30 UTC, Andrei Alexandrescu wrote:
> On 8/25/13 6:16 PM, Paul Jurczak wrote:
>> On Sunday, 25 August 2013 at 23:16:17 UTC, Joseph Rushton Wakeling wrote:
>>> On 26/08/13 01:06, Andrei Alexandrescu wrote:
>>>> This is one of the worst PR functional programming has ever gotten,
>>>> and one of
>>>> the worst things FP has done to the larger community. Somebody should
>>>> do hard
>>>> time for this. And yes, for that matter it's a great example in which
>>>> SLOCs are
>>>> not a very good measure.
>>>
>>> I thought you'd like me bringing this up. ;-)
>>
>> You still have a chance, because I don't quite get it. With the little I
>> know about Haskell, I find this code very elegant. What is wrong with
>> it? Performance?
>
> I ranted about that a couple of times (including during my DConf talk). In brief:
>
> 1. quicksort is based on in-place partition, so at best that example is a different (and less adequate) algorithm inspired from quicksort.
>
> 2. choosing the first element as pivot yields quadratic performance on almost sorted sequence, which is a common practical case.
>
> That example is part of a toxic trifecta (also including the doubly-exponential fibonacci and the O(N) space factorial) that has done a lot of bad teaching.
>
>
> Andrei

@Andrei, @deadalnix, @Meta, @bearophile

I see, performance sucks and this function only kind of looks like a quicksort. It makes sense putting this 'quicksort" and recursive Fibonacci and factorial in the same bag of ivory tower ideas, otherwise known as Haskell. But it looked so nice :-(

On Mon, 2013-08-26 at 00:57 +0200, Joseph Rushton Wakeling wrote:
> On 24/08/13 19:01, Ramon wrote:
> > I think that there is a lot speaking against sloc.
> >
> > First it's often (ab?)used for "Ha! My language x is better than yours. I can write a web server in 3 lines, you need 30".
> 
> Don't know about a web server, but I remember somewhere online I found this really cool 3-line quicksort that you can do in Haskell :-)
> 
>      qsort []     = []
>      qsort (x:xs) = qsort (filter (< x) xs) ++ [x]
>                     ++ qsort (filter (>= x) xs)

OK so good for the first 20s of a lecture on Quicksort and totally useless for doing anything properly. Two main reasons:

1. It copies data rather than doing it in situ, should use Mergesort. 2. passes over the data twice instead of once.

This is a perfect example of where minimizing LOC and doing the right thing are opposed.

-- 
Russel. ============================================================================= Dr Russel Winder      t: +44 20 7585 2200   voip: sip:russel.winder@ekiga.net 41 Buckmaster Road    m: +44 7770 465 077   xmpp: russel@winder.org.uk London SW11 1EN, UK   w: www.russel.org.uk  skype: russel_winder

On 26/08/13 14:04, Russel Winder wrote:
> OK so good for the first 20s of a lecture on Quicksort and totally
> useless for doing anything properly. Two main reasons:
>
> 1. It copies data rather than doing it in situ, should use Mergesort.
> 2. passes over the data twice instead of once.
>
> This is a perfect example of where minimizing LOC and doing the right
> thing are opposed.

If anyone hadn't already realized, my citation of this example was a joke based on the fact that it's explicitly cited in Andrei's article "On iteration" as an example of beautiful-looking code that is terrible in practice.  Or, as he puts it, "Emperors clad in boxers". :-)

Lisp- and Haskell-oriented friends have objected to that example as a strawman, claiming that everyone knows that in practice you implement QuickSort differently, but I think it's an entirely fair critique -- examples like this offer false promises about the practical expressiveness of a language.

On Monday, 26 August 2013 at 12:05:09 UTC, Russel Winder wrote:
> On Mon, 2013-08-26 at 00:57 +0200, Joseph Rushton Wakeling wrote:
>> On 24/08/13 19:01, Ramon wrote:
>> > I think that there is a lot speaking against sloc.
>> >
>> > First it's often (ab?)used for "Ha! My language x is better than yours. I can
>> > write a web server in 3 lines, you need 30".
>> 
>> Don't know about a web server, but I remember somewhere online I found this really cool 3-line quicksort that you can do in Haskell :-)
>> 
>>      qsort []     = []
>>      qsort (x:xs) = qsort (filter (< x) xs) ++ [x]
>>                     ++ qsort (filter (>= x) xs)
>
> OK so good for the first 20s of a lecture on Quicksort and totally
> useless for doing anything properly. Two main reasons:
>
> 1. It copies data rather than doing it in situ, should use Mergesort.
> 2. passes over the data twice instead of once.
>
> This is a perfect example of where minimizing LOC and doing the right
> thing are opposed.

It goes throw data 3 times : to filter (twice) and to to concat at the end.