Jesse Phillips:
http://www.reddit.com/r/programming/comments/a2hv3/on_iteration_by_andrei_alexandrescu/
The article is quite readable and easy to understand. It's a nice paper. Lot of
people don't like C++ and its STL, but this is not important.
Most problems I see in this article are in the "Forward Is Not Enough" part.
>Try defining quicksort in two lines in your Blub language!<
Just for fun, in Python:
from random import randint
data = [randint(200) for _ in xrange(15)]
data
[71, 86, 177, 125, 109, 150, 143, 65, 22, 101, 157, 177, 79, 163, 173]
Q = lambda L: Q([x for x in L[1:] if x<L[0]]) + [L[0]] + Q([x for x in L[1:] if
x>L[0]]) if L else []
Q(data)
[22, 65, 71, 79, 86, 101, 109, 125, 143, 150, 157, 163, 173, 177]
And in D1 using my dlibs:
import d.func, d.random;
T[] Q(T)(T[] L) {
T x;
return len(L) ? Q(select(x, x, L[1..$], x<L[0])) ~ L[0] ~ Q(select(x, x,
L[1..$], x>=L[0])) : null;
}
void main() {
auto data = table(randInt(200), 15);
putr(data, \n, Q(data));
}
For starters, qsort is not really quicksort. Quicksort, as defined by Hoare in his
seminal paper [8], is an in-place algorithm.<
In Haskell (and sometimes in Clojure, Scala, Erlang, etc too) values are
usually immutable, so you can't change arrays in-place.
Hoare's in-place partition is his paper's main contribution and a quintessential
part of quicksort.<
I think functional-minded programmers may not agree with you.
It does so much ancillary work it's not even funny—did you think that those two
passes through the list and all those concatenations come for free?)<
I think the Haskell compiler optimizes some or most of those concatenations
away. And the two separated passes may even became an advantage if you have a
multi-core computer.
Choosing a random pivot is the correct solution,<
The best solution is to choose the median as pivot. Usually you don't know the
median, so you look for its approximation, like choosing a random pivot, or
computing the median of 3 or 9 items.
Singly-linked lists and forward iteration are everything you need. They aren't,
and they shouldn't be made to seem like they are.<
Are we sure Haskell uses single linked lists for that? I think under the cover
the situation is different.
Lisp and other functional languages do offer arrays, but almost invariably as
second-class citizens that don't enjoy the level of language support that S-lists
do.<
Things may be changing, Clojure is a quite Lisp-like language and it has arrays
and associative arrays with a handy syntax.
The name "retro" is not quite fitting, but the more correct "reverser" seemed
forced.<
I think I like "reverser" better, its purpose is more clear.
For example, sort(Chain(a, b, c)) sorts a logical array that has three physical
arrays as support.<
This is very cute, but I have yet to find a situation where it can be useful :-)
I can say that at least some of the reviewers were more able than me to write this
article in the first place, both from a technical and a literary perspective.<
This happens all the time among programmers, writers of novels and short
stories, and so on. But it doesn't matter, the one that has written the article
is you, not them. Keep writing. And keep in mind that few more iterations of
improvements in the design of the std lib may follow :-)
Bye,
bearophile
