[Haskell-cafe] Can Haskell outperform C++?

[Richard O'Keefe]

On 17/05/2012, at 10:07 PM, Roman Werpachowski wrote:
>> No slide deck required.  The task is "generating alternating permutations".
>> 
>> Method 1: generate permutations using a backtracking search;
>>          when a permutation is generated, check if it is alternating.
>> 
>> Method 2: use the same backtracking search, but only allow extensions
>>          that preserve the property of being an alternating permutation.
> 
> Gregg,
> 
> what makes Method 2 so much harder than Method 1 to implement in C or C++?


It was me, not Gregg.  There was and is no claim that method 2 is "much harder
to implement in C or C++".  In fact both methods *were* implemented easily in C.
The claim was and remains solely that
THE TIME DIFFERENCE BETWEEN *ALGORITHMS*
   can be bigger than
THE TIME DIFFERENCE BETWEEN *LANGUAGES*
   and is in this particular case.

(And that's despite the fact that the C version kept the set of unused
elements as a one-native-word bit mask, while the Prolog version kept it
as a linked list.) 

There is also a second claim, which I thought was uncontentious:
the relative difficulty of tasks varies with language.