Parallel Rogue-like benchmark

[bearophile]

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