On Iteration By Andrei Alexandrescu

bearophile bearophileHUGS at lycos.com
Mon Nov 9 13:21:27 PST 2009


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


More information about the Digitalmars-d-announce mailing list