• Jesse Phillips (5/5) Nov 09 2009 This has a strange hick-up in the intro, "Andrei Alexandrescu, author of...
• Jesse Phillips (2/8) Nov 09 2009 Damn it, I just realized, author of "The D Programming Language" :P
• bearophile (28/43) Nov 09 2009 The article is quite readable and easy to understand. It's a nice paper....
• Spacen Jasset (18/99) Nov 13 2009 I am quite glad that D2's standard library does not follow doggedly the
• Max Samukha (3/8) Nov 09 2009 Good stuff! Just feels right.

Jesse Phillips <jessekphillips gmail.com> writes:

This has a strange hick-up in the intro, "Andrei Alexandrescu, author of 
The D Programming Language" I sent them a message, so it should get fixed 
but :D

http://www.reddit.com/r/programming/comments/a2hv3/
on_iteration_by_andrei_alexandrescu/

Jesse Phillips <jessekphillips gmail.com> writes:

On Mon, 09 Nov 2009 15:24:48 +0000, Jesse Phillips wrote:

 This has a strange hick-up in the intro, "Andrei Alexandrescu, author of
 The D Programming Language" I sent them a message, so it should get
 fixed but :D
 
 http://www.reddit.com/r/programming/comments/a2hv3/
 on_iteration_by_andrei_alexandrescu/

Damn it, I just realized, author of "The D Programming Language" :P

bearophile <bearophileHUGS lycos.com> writes:

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

Spacen Jasset <spacenjasset yahoo.co.uk> writes:

bearophile wrote:
 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

I am quite glad that D2's standard library does not follow doggedly the 
path of the STL, however conceptually neat it may be. Ranges do seem to 
be the way forward, but alas I haven't been following D2 that closely. I 
feel compelled to say one thing further though that, unfortunately, is 
backed by pure ether (or opinion).



expressiveness of the STL, but instead went for a more (seemingly to 
it's users) utilitarian approach, which, as you have pointed out can 
sometimes be awkward, inflexible, or inefficient. But I ask myself why 
that is the case? It's because the STL is to many people impermeable, 
and too far removed from the problem they are trying to solve. In fact 

see why.

We're all here in this group because there is something about D, and
I look forward to the book, and I will take stock again and see if it 
that thing I hope it would develop into when I first discovered it some 
years ago.

Max Samukha <spambox d-coding.com> writes:

On Mon, 9 Nov 2009 15:24:48 +0000 (UTC), Jesse Phillips
<jessekphillips gmail.com> wrote:

This has a strange hick-up in the intro, "Andrei Alexandrescu, author of 
The D Programming Language" I sent them a message, so it should get fixed 
but :D

http://www.reddit.com/r/programming/comments/a2hv3/
on_iteration_by_andrei_alexandrescu/

Good stuff! Just feels right.