On Iteration By Andrei Alexandrescu

[Spacen Jasset]

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).


Languages such as C# or Java may not have appeared to head the 
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 
many a time the STL seems a madness to C# and Java programmers. I can 
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.