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
