May 28, 2013
Andrei Alexandrescu:

> I'm disappointed cartesianProduct works that way; I should have caught that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.

I opened this:
http://d.puremagic.com/issues/show_bug.cgi?id=9878

Bye,
bearophile
May 28, 2013
On 5/27/13 9:30 PM, Peter Williams wrote:
> On 28/05/13 10:37, bearophile wrote:
>>> .map!(words => words
>>> .classify!q{ a
>>> .dup
>>> .representation
>>> .sort()
>>> .release
>>
>> Also, let's kill the built-in sort already :-)
>>
>
> But I just found it and started using it. :-)
>
> I was contemplating writing my own sort function as the ones in
> std.algorithm didn't meet my needs (or using them was too messy) until I
> discovered this feature.

We need to fix that! std.algorithm.sort should include builtin sort's functionality,

Andrei


May 28, 2013
Andrei Alexandrescu:

> We need to fix that! std.algorithm.sort should include builtin sort's functionality,

What is the missing functionality we are talking about?
I think the only advantage of the built-in sort is that it causes less template bloat and less compilation time.

Anyway, I'd like to see a warning or deprecation for the built-in sort soon... Unless you/we want to un-deprecate it and fix it better. Keeping several things for lot of time in a "will-be-deprecated" limbo doesn't sound good for a serious language.

Bye,
bearophile
May 28, 2013
On 5/27/2013 5:16 PM, bearophile wrote:
> There are several optimizations that D/DMD is not performing on those ranges and
> higher order functions. The Haskell compiler GHC optimized that stuff using
> purity, library defined "rewrite rules", stream fusion/deforestation and more.
> DMD does nothing of this, or very little. I think so far Walter has shown no
> interest in this.

I don't really know what you're talking about.
May 28, 2013
On Mon, May 27, 2013 at 10:01:32PM -0400, Andrei Alexandrescu wrote:
> On 5/27/13 5:36 PM, bearophile wrote:
> >This simple example shows the difference:
> >
> >import std.stdio, std.algorithm;
> >void main() {
> >auto data = [1, 2, 3, 4];
> >foreach (xy; cartesianProduct(data, data))
> >writeln(xy);
> >}
> >
> >
> >Generates the tuples:
> >(1, 1)
> >(2, 1)
> >(3, 1)
> >(4, 1)
> >(1, 2)
> >(2, 2)
> >(3, 2)
> >(4, 2)
> >(1, 3)
> >(2, 3)
> >(3, 3)
> >(4, 3)
> >(1, 4)
> >(2, 4)
> >(3, 4)
> >(4, 4)
> 
> I'm disappointed cartesianProduct works that way; I should have caught that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.

This is not too hard to change; it's just a matter of swapping left- and right- recursion in the templates. I'll see if I can cook up an pull request in a bit.


T

-- 
It only takes one twig to burn down a forest.
May 28, 2013
On Tuesday, May 28, 2013 03:50:48 bearophile wrote:
> Peter Williams:
> > Are the () necessary on sort?
> 
> If you don't use () I think you call the slower, not flexible and buggy built-in sort. I think it's already deprecated. Maybe I am wrong...

If it's on an array, then yes, I believe that calling sort without parens would call the built-in one that should be deprecated.

- Jonathan M Davis
May 28, 2013
On Mon, May 27, 2013 at 07:35:36PM -0700, H. S. Teoh wrote:
> On Mon, May 27, 2013 at 10:01:32PM -0400, Andrei Alexandrescu wrote:
> > On 5/27/13 5:36 PM, bearophile wrote:
> > >This simple example shows the difference:
> > >
> > >import std.stdio, std.algorithm;
> > >void main() {
> > >auto data = [1, 2, 3, 4];
> > >foreach (xy; cartesianProduct(data, data))
> > >writeln(xy);
> > >}
> > >
> > >
> > >Generates the tuples:
> > >(1, 1)
> > >(2, 1)
> > >(3, 1)
> > >(4, 1)
> > >(1, 2)
> > >(2, 2)
> > >(3, 2)
> > >(4, 2)
> > >(1, 3)
> > >(2, 3)
> > >(3, 3)
> > >(4, 3)
> > >(1, 4)
> > >(2, 4)
> > >(3, 4)
> > >(4, 4)
> > 
> > I'm disappointed cartesianProduct works that way; I should have caught that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.
> 
> This is not too hard to change; it's just a matter of swapping left- and right- recursion in the templates. I'll see if I can cook up an pull request in a bit.
[...]

Done, turns out the fix was trivial, just swapping two static ifs:

https://github.com/D-Programming-Language/phobos/pull/1314


T

-- 
I think Debian's doing something wrong, `apt-get install pesticide', doesn't seem to remove the bugs on my system! -- Mike Dresser
May 28, 2013
> Done, turns out the fix was trivial, just swapping two static ifs: https://github.com/D-Programming-Language/phobos/pull/1314

This isn't what Andrei had in mind in his post above:

> I'm disappointed cartesianProduct works that way; I should have caught
that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.

I would suggest an additional template parameter to specify the order of
iteration:
for example an enum Order {lexicographic_depth,
lexicographic_breadth,antilexicographic_depth,
antilexicographic_breadth}.
The naming is horrible but you get the idea:
cartesianProduct!(order)(['a','b','c'],[1,2,3]))
order=Order.lexicographic_depth:
a1 a2 a3 b1 b2 b3 c1 c2 c3
order=Order. lexicographic_breadth:
a1 b1 a2 c1 b2 a3 c2 b3 c3
ie , in 2D, it follows diagonals x+y=k, with k=0,1,2,... and 0<=x<length(x
range), 0<=y<length(y range)
order=Order.antilexicographic_depth:
a1 b1 c1 a2 b2 c2 a3 b3 c3
order=Order.antilexicographic_breadth:
a1 a2 b1 a3 b2 c1 b3 c2 c3


On Mon, May 27, 2013 at 7:58 PM, H. S. Teoh <hsteoh@quickfur.ath.cx> wrote:

> On Mon, May 27, 2013 at 07:35:36PM -0700, H. S. Teoh wrote:
> > On Mon, May 27, 2013 at 10:01:32PM -0400, Andrei Alexandrescu wrote:
> > > On 5/27/13 5:36 PM, bearophile wrote:
> > > >This simple example shows the difference:
> > > >
> > > >import std.stdio, std.algorithm;
> > > >void main() {
> > > >auto data = [1, 2, 3, 4];
> > > >foreach (xy; cartesianProduct(data, data))
> > > >writeln(xy);
> > > >}
> > > >
> > > >
> > > >Generates the tuples:
> > > >(1, 1)
> > > >(2, 1)
> > > >(3, 1)
> > > >(4, 1)
> > > >(1, 2)
> > > >(2, 2)
> > > >(3, 2)
> > > >(4, 2)
> > > >(1, 3)
> > > >(2, 3)
> > > >(3, 3)
> > > >(4, 3)
> > > >(1, 4)
> > > >(2, 4)
> > > >(3, 4)
> > > >(4, 4)
> > >
> > > I'm disappointed cartesianProduct works that way; I should have caught that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.
> >
> > This is not too hard to change; it's just a matter of swapping left- and right- recursion in the templates. I'll see if I can cook up an pull request in a bit.
> [...]
>
> Done, turns out the fix was trivial, just swapping two static ifs:
>
> https://github.com/D-Programming-Language/phobos/pull/1314
>
>
> T
>
> --
> I think Debian's doing something wrong, `apt-get install pesticide', doesn't seem to remove the bugs on my system! -- Mike Dresser
>


May 28, 2013
On Mon, May 27, 2013 at 09:24:28PM -0700, Timothee Cour wrote:
> > Done, turns out the fix was trivial, just swapping two static ifs: https://github.com/D-Programming-Language/phobos/pull/1314
> 
> This isn't what Andrei had in mind in his post above:
> 
> > I'm disappointed cartesianProduct works that way; I should have caught that during the code review. A better iteration order would have spanned the lower position in both ranges first, i.e. create squares of increasing side in the 2D space.
> 
> I would suggest an additional template parameter to specify the order of iteration:
[...]

The problem with allowing the user to specify order is that when one or more of the input ranges are infinite, the order of traversal is much less flexible, and it may not be possible to satisfy the requested order.

The order that Andrei suggested is what's currently used for two infinite ranges, though when finite ranges are involved I chose a slightly simpler implementation. The order bearophile proposed in issue 9878 is different from what Andrei describes, at any rate.

What's the typical output order of cartesian products in other languages / libraries? It seems nobody can agree on what the order should be. :-/


T

-- 
People demand freedom of speech to make up for the freedom of thought which they avoid. -- Soren Aabye Kierkegaard (1813-1855)
May 28, 2013
On 28/05/13 11:50, bearophile wrote:
> Peter Williams:
>
>> Are the () necessary on sort?
>
> If you don't use () I think you call the slower, not flexible and buggy
> built-in sort. I think it's already deprecated. Maybe I am wrong...

Ah.  Does that mean that import.algorithms is need to use sort()?

>
>
>> PS Now I've found this I can go back and simplify all the code where I
>> iterated over associative arrays in key order by getting the keys and
>> the sorting them separately.
>
> I don't fully understand.

I'm assuming here that it's safe to call sort() on the .keys property of the dynamic array.  This enables me to go:

foreach (key; aa.keys.sort()) {...}

instead of the much more complex code I'm currently writing which gets the keys, sorts them and then uses them in the foreach.  I had actually written a generic function to do all of that but now find all the work was unnecessary :-).

As I learn more about D I'm finding I can go back and simplify a lot of my code.  I'm going to reread Andrei's book to see what I missed the first time.

Peter
PS I think I need to read more about component programming as I'm beginning to suspect I don't understand it fully.