www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.announce - On Iteration By Andrei Alexandrescu

reply 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/
Nov 09 2009
next sibling parent 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
Nov 09 2009
prev sibling next sibling parent reply 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
Nov 09 2009
parent 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.
Nov 13 2009
prev sibling parent 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.
Nov 09 2009