Parallel Rogue-like benchmark

[Paul Jurczak]

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 :-(