www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - More on "Component Programming"

reply "bearophile" <bearophileHUGS lycos.com> writes:
This simple task on Rosettacode site is useful to show some uses 
of Phobos and the "component programming" recently discussed by 
Walter (other languages use a different name to denote the same 
idea).

Given a dictionary file of different words, it asks to find any 
of the longest anagram pairs, that also share no equal chars in 
the same position (so they are named deranged anagrams):

http://rosettacode.org/wiki/Anagrams/Deranged_anagrams#D

There are many ways to do this in D+Phobos. The following 
solution is long, but it's quite fast (the "warmed up" run-time 
is only about 0.03 seconds with a dictionary of about 200 KB, on 
an old CPU core), I have chosen it over simple solutions because 
it gives me a chance to discuss certain things:



import std.stdio, std.file, std.algorithm, std.string,
        std.typecons, std.range, std.functional;

auto findDeranged(in string[] words) pure /*nothrow*/ {
     //return words.pairwise.filter!(ww=> ww[].zip.all!q{a[0] != 
a[1]});
     Tuple!(string, string)[] result;
     foreach (immutable i, const w1; words)
         foreach (const w2; words[i + 1 .. $])
             if (zip(w1, w2).all!q{ a[0] != a[1] })
                 result ~= tuple(w1, w2);
     return result;
}

void main() {
     Appender!(string[])[30] wClasses;
     foreach (word; 
std.algorithm.splitter("unixdict.txt".readText))
         wClasses[$ - word.length] ~= word;

     "Longest deranged anagrams:".writeln;
     foreach (words; wClasses[].map!q{ a.data 
}.filter!(not!empty)) {
         string[][const ubyte[]] anags; // Assume ASCII input.
         foreach (w; words)
             anags[w.dup.representation.sort().release.idup] ~= w;
         auto pairs = anags.byValue.map!findDeranged.join;
         if (!pairs.empty)
             return writefln("  %s, %s", pairs.front[]);
     }
}


- - - - - - - - - - - -

That program contains five foreach loops. Foreach loops are not 
evil and I like them, but for a certain kind of programming 

languages) every time you use a for/foreach it's one small 
"failure" for the standard library :-)

The following weird (untested and maybe buggy) program replaces 
all the foreach loops with higher order functions and other 
library functions. It can't be compiled because it uses some 
things not yet present in Phobos (on the Rosettacode page there 
is also a slower and simpler D solution of this problem that uses 
only one foreach):


void main() {
     import std.stdio, std.file, std.algorithm, std.string,
            std.typecons, std.range, std.functional;

     "unixdict.txt"
     .readText
     .splitter
     .classify!q{ a.length }
     .map!q{ a.values } // .byValue is almost OK.
     .array
     .schwartzSort!q{ -a[0].length }
     .release
     .map!(words => words
                    .classify!q{ a
                                 .dup
                                 .representation
                                 .sort()
                                 .release
                                 .idup }
                    .byValue
                    .map!(words => words
                                   .pairwise
                                   .filter!(ww => ww[]
                                                  .zip
                                                  .all!q{ a[0] != 
a[1] }))
                    .join)
     .filter(not!empty)
     .front[]
     .binaryReverseArgs!writefln("  %s, %s");
}


A copy of the same code if the newsgroup has messed up the 
formatting and indents, turning that code into a soup:
http://codepad.org/L4TyDkcQ


I am not suggesting you to write whole D script-like programs in 
this strange style. But I think Phobos should offer all the tools 
to write a program like this, because even if you don't want to 
write a whole little program in this style, you sometimes want to 
use some parts of it or some other parts of it, so I think all 
the most common and distinct micro-patterns should be contained 
in Phobos.

- - - - - - - - - - - -

"binaryReverseArgs" is in the std.functional module. Here it 
allows the use of writefln in UFCS style, inverting the 
formatting string position. I think I'd like a shorter and more 
handy name for it. In Haskell it's named "flip", and its usage is 
not uncommon.

- - - - - - - - - - - -

"classify" is a simple function, that given a forward range of T 
and an optional function T->K, returns an associative array 
T[][K]. (Arrays are used by default as values. But maybe you can 
optionally specify a different type of values, like Appenders, 
Arrays, sets, etc). (Currently in Phobos the only function to 
build an associative array is std.array.assocArray, but here we 
need something different). 
(http://d.puremagic.com/issues/show_bug.cgi?id=5502 ).

[1, 7, 6, 3, 2].classify!(x => x % 2 ? "odd": "even").writeln;

==>
["odd": [1, 7, 3], "even": [6, 2]]

- - - - - - - - - - - -

"pairwise" is a very useful lazy range similar to 
cartesianProduct, but it yields only the ordered pairs, so they 
cover only about half (a triangle) of the square matrix of the 
possibilities. 
(http://d.puremagic.com/issues/show_bug.cgi?id=6788 ).


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)


While:

import std.stdio, std.range;
void main() {
     auto data = [1, 2, 3, 4];
     foreach (tup; pairwise(data))
         writeln(tup);
}


Should generate:
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)


In the Python standard library there is a lazy generator that's 
more general than pairwise:

 from itertools import combinations
 list(combinations([1, 2, 3, 4], 2))
[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)] So if you prefer that more general solution the D code becomes: ... .map!(words => words .combinations(2) .filter!(ww => ww[] ... Bye, bearophile
May 27 2013
next sibling parent reply "Sebastian Graf" <SebastianGraf t-online.de> writes:
On Monday, 27 May 2013 at 21:36:12 UTC, bearophile wrote:
 snip
Every time I see that kind of code, my heart makes a delightful jump. That code is what I enjoy most about D compared to C++. Plus, the compiler is still able to optimize most of the I'm all for more algorithm primitives in std.algorithm. I missed confused that std.algorithm.group did not what I thought it did. Is there any reason why you keep using quoted strings instead of string literals for lambdas besides taste?
May 27 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Sebastian Graf:

 Plus, the compiler is still able to optimize most of the 

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'm all for more algorithm primitives in std.algorithm. I 

 was confused that std.algorithm.group did not what I thought it 
 did.

 std.algorithm.group did not what I thought it did.
The "group" of Phobos is useful and it has purposes quite different from the Perl6 "classify", both are needed. I have also suggested "group" to act more like the Python "itertools.grouby" and yield not just the (head,count) tuples, but (head,lazy_range_of_the_equality_ class) that is quite useful, example:
 from itertools import groupby
 s = "abABACAaaaaBCAB"
 [(h, list(g)) for h,g in groupby(s, key=str.isupper)]
[(False, ['a', 'b']), (True, ['A', 'B', 'A', 'C', 'A']), (False, ['a', 'a', 'a', 'a']), (True, ['B', 'C', 'A', 'B'])] I think Andrei was looking at this change with interest. Changing Phobos group() API now is maybe not easy to do, so maybe it's better to introduce a differently named function for that, like one named "groupAll" or something similar.
 Is there any reason why you keep using quoted strings instead 
 of string literals for lambdas besides taste?
My editor uses a single uniform color for the contents of normal strings, unlike quoted strings. Bye, bearophile
May 27 2013
next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 28, 2013 at 02:16:22AM +0200, bearophile wrote:
 Sebastian Graf:
 
Plus, the compiler is still able to optimize most of the

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.
Library-defined rewrite rules would be über-cool if it were supported in D. *(waits for somebody to mention "AST macros", and everyone else to shout him down. :-P)
 DMD does nothing of this, or very little. I think so far Walter has
 shown no interest in this.
[...] The DMD optimizer certainly leaves a lot of room for improvement. I think Walter would accept pull requests to that effect. ;-) T -- Try to keep an open mind, but not so open your brain falls out. -- theboz
May 27 2013
prev sibling next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 5/27/13 8:16 PM, bearophile wrote:
 The "group" of Phobos is useful and it has purposes quite different from
 the Perl6 "classify", both are needed.
 I have also suggested "group" to act more like the Python
 "itertools.grouby" and yield not just the (head,count) tuples, but
 (head,lazy_range_of_the_equality_ class) that is quite useful, example:


 from itertools import groupby
 s = "abABACAaaaaBCAB"
 [(h, list(g)) for h,g in groupby(s, key=str.isupper)]
[(False, ['a', 'b']), (True, ['A', 'B', 'A', 'C', 'A']), (False, ['a', 'a', 'a', 'a']), (True, ['B', 'C', 'A', 'B'])] I think Andrei was looking at this change with interest. Changing Phobos group() API now is maybe not easy to do, so maybe it's better to introduce a differently named function for that, like one named "groupAll" or something similar.
I wrote that a while ago. Someone please review and pull https://github.com/D-Programming-Language/phobos/pull/1186 already! Andrei
May 27 2013
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
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 27 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Walter Bright:

 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.
Then maybe you have missed the last two times I have discussed such topics in D.learn. They are optimizations done by compilers of functional languages, in particular the GHC compiler of the lazy functional language Haskell. The optimizations performed thanks to purity and immutability are needed by GHC because in Haskell you use Higher Order Functions (HOFs), and generally you use functions as first class immutable values, so if you don't inline a lot, your Haskell program will be slow as a snail. The "rewrite rules" is a feature of the GHC compiler. It allows the library writers to define rules that in most (or many) cases are advantageous and lead to better optimization. As example one of such rules swap map and filter, putting the filter before the map, because this is more efficient. Haskell allows you to perform such swapping because (nearly) everything it does is pure and immutable. Some examples and explanations on the GHC rewrite rules: http://www.haskell.org/ghc/docs/7.0.1/html/users_guide/rewrite-rules.html http://www.haskell.org/haskellwiki/GHC/Using_rules http://www.haskell.org/haskellwiki/Playing_by_the_rules Stream fusion, or more generally deforestation is another optimization done by GHC, it's needed because it's a functional language that uses lists all the time, and such optimization are helped by Haskell default lazyness (deforestation is possible in an eager language too, but it's a bit less easy to do, they say). If you perform a map and then a filter and then another HOF you are traversing lists all the time, and this is slow. Haskell default strings currently are lists of chars, so you have to optimize string operations well. To generate fast binaries GHC "fuses" similar lazy streams, and avoids creating all the intermediate lists. With this optimization recently GHC has shown to generate good enough vectorized SSE-aware binaries that are faster than naive C code optimized by the vectorizing stages of the GCC optimizer, and beaten only by very vector-intrinsics-heavy handwritten C code: http://research.microsoft.com/en-us/um/people/simonpj/papers/ndp/haskell-beats-C.pdf But that's not a paper to start reading about such topics, because that's a late paper on the topic. More on the topic: http://www.randomhacks.net/articles/2007/02/10/map-fusion-and-haskell-performance On the topic there are both easy to understand and harder to understand papers. So you have to choose. Bye, bearophile
May 28 2013
next sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Tuesday, 28 May 2013 at 09:54:35 UTC, bearophile wrote:
 The "rewrite rules" is a feature of the GHC compiler. It allows 
 the library writers to define rules that in most (or many) 
 cases are advantageous and lead to better optimization. As 
 example one of such rules swap map and filter, putting the 
 filter before the map, because this is more efficient. Haskell 
 allows you to perform such swapping because (nearly) everything 
 it does is pure and immutable.
Phobos does this a little bit in simple cases. For example, retro(retro(r)) returns r if I remember correctly. More complicated rewrites would be trickier to implement, and may be impossible cross-modules (I cannot provide a rewrite for retro(my.module.range) without modifying Phobos). General rewrites, like the kind relational database query optimisers do, require statistics on the data structures. For example: 1) cartesianProduct(r1, r2).filter!(pred).sort("a[1]<b[1]") 2) cartesianProduct(r1, r2.sort("a[1]<b[1]")).filter!(pred) Which is faster depends on the sizes of r1 and r2, and the pass ratio of the filter predicate.
May 28 2013
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 19:55:43 Peter Alexander wrote:
 Phobos does this a little bit in simple cases. For example,
 retro(retro(r)) returns r if I remember correctly.
Yes. Phobos tries to optimize useless templates like that, and definitely does it in this particular case, though I don't know if it does it everywhere that it should.
 More complicated rewrites would be trickier to implement, and may
 be impossible cross-modules (I cannot provide a rewrite for
 retro(my.module.range) without modifying Phobos).
True, though you might be able to pull off something very close with alias this. The type wouldn't be the same, but it would at least convert to the same type. - Jonathan M Davis
May 28 2013
prev sibling next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 5/28/2013 2:54 AM, bearophile wrote:
 The "rewrite rules" is a feature of the GHC compiler. It allows the library
 writers to define rules that in most (or many) cases are advantageous and lead
 to better optimization. As example one of such rules swap map and filter,
 putting the filter before the map, because this is more efficient. Haskell
 allows you to perform such swapping because (nearly) everything it does is pure
 and immutable.
Thank you.
May 28 2013
prev sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
 Then maybe you have missed the last two times I have discussed 
 such topics in D.learn.
Sorry, I meant the main D newsgroup. Bye, bearophile
May 28 2013
prev sibling next sibling parent reply "Sebastian Graf" <SebastianGraf t-online.de> writes:
On Tuesday, 28 May 2013 at 00:16:23 UTC, bearophile wrote:
 Sebastian Graf:

 Plus, the compiler is still able to optimize most of the 

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.
Point taken, but what I actually meant was that the compiler is allowed to optimize it all away in _theory_. You cannot have this big array is faster with a foreach-if combination than with an array.Where(predicate) linq statement (I blame the cache and delegate indirection). Since there is no strong compile time templating, this will not change in the future. Of course this is a very specific case, but it is something you have to keep in mind. The difference for some MB-sized arrays is noticable. TIL that GHC already has this. I should really continue learning Haskell.
May 28 2013
parent "Paulo Pinto" <pjmlp progtools.org> writes:
On Tuesday, 28 May 2013 at 07:26:06 UTC, Sebastian Graf wrote:
 On Tuesday, 28 May 2013 at 00:16:23 UTC, bearophile wrote:
 Sebastian Graf:

 Plus, the compiler is still able to optimize most of the 

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.
Point taken, but what I actually meant was that the compiler is allowed to optimize it all away in _theory_. You cannot have big array is faster with a foreach-if combination than with an array.Where(predicate) linq statement (I blame the cache and delegate indirection). Since there is no strong compile time templating, this will not change in the future. Of course this is a very specific case, but it is something you have to keep in mind. The difference for some MB-sized arrays is noticable. TIL that GHC already has this. I should really continue learning Haskell.
Even with NGEN or Mono -aot?
May 28 2013
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2013-05-28 02:16, bearophile wrote:

 My editor uses a single uniform color for the contents of normal
 strings, unlike quoted strings.
Why not use proper lambdas instead of strings? -- /Jacob Carlborg
May 28 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Jacob Carlborg:

 Why not use proper lambdas instead of strings?
Mostly for personal reasons: quoted strings are sometimes a little shorter, and they require you to use arguments with default names (as "a" and "b"), this increased standardization makes me read them a little faster than lambdas that have varying argument names. If I see q{a + b} I don't need to go look what a and b are, for me it's a "standard" sum, like one to be used by a reduce(). It's a bit like the "pointfree" style in Haskell (http://www.haskell.org/haskellwiki/Pointfree ), also named "tacit" in other languages, where you don't name input variables; that if overused makes the code unreadable, but if used a bit and wisely allows you to underline the transformations done on the data instead of on the (sometimes arbitrary) names you give to parts of generic data. Bye, bearophile
May 28 2013
prev sibling parent "Paulo Pinto" <pjmlp progtools.org> writes:
On Monday, 27 May 2013 at 23:23:52 UTC, Sebastian Graf wrote:
 On Monday, 27 May 2013 at 21:36:12 UTC, bearophile wrote:
 snip
Every time I see that kind of code, my heart makes a delightful jump. That code is what I enjoy most about D compared to C++. Plus, the compiler is still able to optimize most of the I'm all for more algorithm primitives in std.algorithm. I was confused that std.algorithm.group did not what I thought it did. Is there any reason why you keep using quoted strings instead of string literals for lambdas besides taste?
Microsoft could actually spend a bit more time on their optimizer, but I guess business has other priorities.
May 28 2013
prev sibling next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
     .map!(words => words
                    .classify!q{ a
                                 .dup
                                 .representation
                                 .sort()
                                 .release
Also, let's kill the built-in sort already :-) Bye, bearophile
May 27 2013
next sibling parent reply Peter Williams <pwil3058 bigpond.net.au> writes:
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. Are the () necessary on sort? I found: auto sorted_array = an_array.dup.sort; worked. Peter 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. PPS Every time I discover one of these features I like D even more.
May 27 2013
next sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
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...
 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. Bye, bearophile
May 27 2013
next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
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 27 2013
prev sibling parent Peter Williams <pwil3058 bigpond.net.au> writes:
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.
May 27 2013
prev sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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 27 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
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 27 2013
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Tuesday, May 28, 2013 11:30:55 Peter Williams wrote:
 Are the () necessary on sort?  I found:
 
 auto sorted_array = an_array.dup.sort;
Any function which takes no arguments can be called without parens, and thanks to UFCS (Universal Function Call Syntax), you're calling these functions as if they were member functions and so they no longer have any arguments between the parens and so can be called without parens. - Jonathan M Davis
May 27 2013
prev sibling next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
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. Andrei
May 27 2013
next sibling parent "bearophile" <bearophileHUGS lycos.com> writes:
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 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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 27 2013
prev sibling next sibling parent Timothee Cour <thelastmammoth gmail.com> writes:
 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 27 2013
prev sibling next sibling parent "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
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 27 2013
prev sibling next sibling parent reply Timothee Cour <thelastmammoth gmail.com> writes:
On Mon, May 27, 2013 at 9:53 PM, H. S. Teoh <hsteoh quickfur.ath.cx> wrote:

 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.
Explicit is better than implicit. The user should request the order, and the compiler can statically disallow lexicographic_depth/antilexicographic_depth when at least one of the ranges is infinite.
 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. :-/
python uses itertools.product which is lexicographic_depth. Like you say, no-one can agrees what the order should be, so let's leave it up to user through a template. Sounds like a no-brainer to me. There are use cases for each order I mentioned.
 T

 --
 People demand freedom of speech to make up for the freedom of thought
 which they avoid. -- Soren Aabye Kierkegaard (1813-1855)
May 27 2013
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Timothee Cour:

 python uses itertools.product which is lexicographic_depth.
 Like you say, no-one can agrees what the order should be, so 
 let's leave it
 up to user through a template. Sounds like a no-brainer to me. 
 There are
 use cases for each order I mentioned.
Different cases enjoy different orderings, so giving it a compile-time enum is OK. But I prefer the order of 9878 to be the default one, because it's the most commonly needed by me, and it's what I expect when I port Python code to D. Bye, bearophile
May 28 2013
parent reply "H. S. Teoh" <hsteoh quickfur.ath.cx> writes:
On Tue, May 28, 2013 at 11:37:06AM +0200, bearophile wrote:
 Timothee Cour:
 
python uses itertools.product which is lexicographic_depth.  Like you
say, no-one can agrees what the order should be, so let's leave it up
to user through a template. Sounds like a no-brainer to me.  There
are use cases for each order I mentioned.
Different cases enjoy different orderings, so giving it a compile-time enum is OK. But I prefer the order of 9878 to be the default one, because it's the most commonly needed by me, and it's what I expect when I port Python code to D.
[...] OK, I'm looking at the code to see how this could be implemented, and it seems to require some complications: If both ranges are infinite, then the ordering needs to be Andrei's suggested ordering (incremental 2D square). It *can* have other orderings too, like diagonals, but that requires bidirectional ranges, not just forward ranges. If only one range is infinite, then it is allowed to be an input range, but that constrains it to a specific ordering (namely, finite range first, then increment infinite range). If the infinite range is more than an input range, then of course other orderings are possible, but explicitly supporting those cases seems to be a lot of work for very little added value. If both ranges are finite, then many different orderings are possible, but again it depends on the nature of the ranges. If one of them is an input range, then the other must be a forward range, and the order is constrained. The biggest problem here is, what should be the default ordering for the template? There is no single ordering that will work for every case. Furthermore, how many different kinds of orderings should be supported? There are a lot of possibilities, even just in the finite case (if the ranges are both bidirectional, for example -- who's to say we should exclude a Peano-curve traversal of the cartesian product, or everything in between?). Even restricting ourselves to the simplest orderings, there's the question of how to efficiently implement something like Andrei's 2D traversal when you have two finite ranges of different lengths. Currently, I'm inclined to say, the library gets to decide on the ordering based on its inputs. I'd rather the template require minimal functionality from its input ranges and automatically decide on which ordering is best. I'd just follow bearophile's suggestion for the finite case -- the ordering in issue 9878 is certainly the most useful, and most likely expected (most uses of cartesian products would expect an ordering analogous to binary enumeration, I think). While adding an enum to specify the exact ordering is certainly possible, I'm not sure if it's adding enough value to justify the complications in the implementation. T -- Gone Chopin. Bach in a minuet.
May 28 2013
parent "Diggory" <diggsey googlemail.com> writes:
On Tuesday, 28 May 2013 at 17:24:13 UTC, H. S. Teoh wrote:
 On Tue, May 28, 2013 at 11:37:06AM +0200, bearophile wrote:
 Timothee Cour:
 
python uses itertools.product which is lexicographic_depth.  
Like you
say, no-one can agrees what the order should be, so let's 
leave it up
to user through a template. Sounds like a no-brainer to me.  
There
are use cases for each order I mentioned.
Different cases enjoy different orderings, so giving it a compile-time enum is OK. But I prefer the order of 9878 to be the default one, because it's the most commonly needed by me, and it's what I expect when I port Python code to D.
[...] OK, I'm looking at the code to see how this could be implemented, and it seems to require some complications: If both ranges are infinite, then the ordering needs to be Andrei's suggested ordering (incremental 2D square). It *can* have other orderings too, like diagonals, but that requires bidirectional ranges, not just forward ranges. If only one range is infinite, then it is allowed to be an input range, but that constrains it to a specific ordering (namely, finite range first, then increment infinite range). If the infinite range is more than an input range, then of course other orderings are possible, but explicitly supporting those cases seems to be a lot of work for very little added value. If both ranges are finite, then many different orderings are possible, but again it depends on the nature of the ranges. If one of them is an input range, then the other must be a forward range, and the order is constrained. The biggest problem here is, what should be the default ordering for the template? There is no single ordering that will work for every case. Furthermore, how many different kinds of orderings should be supported? There are a lot of possibilities, even just in the finite case (if the ranges are both bidirectional, for example -- who's to say we should exclude a Peano-curve traversal of the cartesian product, or everything in between?). Even restricting ourselves to the simplest orderings, there's the question of how to efficiently implement something like Andrei's 2D traversal when you have two finite ranges of different lengths. Currently, I'm inclined to say, the library gets to decide on the ordering based on its inputs. I'd rather the template require minimal functionality from its input ranges and automatically decide on which ordering is best. I'd just follow bearophile's suggestion for the finite case -- the ordering in issue 9878 is certainly the most useful, and most likely expected (most uses of cartesian products would expect an ordering analogous to binary enumeration, I think). While adding an enum to specify the exact ordering is certainly possible, I'm not sure if it's adding enough value to justify the complications in the implementation. T
I don't think the ordering should change just because the input type is changed, that would be very confusing, especially when code is just passing on ranges it's received from somewhere else. The default should be the simplest ordering (across then down) and other orderings must be explicitly asked for. When an incompatible ordering (including using an infinite range for the "across" range with the default ordering) is being used it should show a helpful error message suggesting a compatible ordering. There could also be an ordering constant "dontCare" which simply picks any ordering compatible with the nature of the input ranges. I don't think this should be the default because the common case is that you do care what the ordering is, you should have to explicitly say that you don't care. It's also worth mentioning that the rules are more complicated than have been suggested - using an infinite range with the default ordering is fine as long as a finite range is used for the range that is being iterated over more quickly.
May 28 2013
prev sibling parent "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Tuesday, 28 May 2013 at 02:01:30 UTC, Andrei Alexandrescu 
wrote:
 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.
Why is that better? It would be both unexpected and almost certainly slower. It has the advantage that it works sensibly with infinite ranges, but I think the correct approach would be to provide a policy option for the iteration strategy (lexicographic, colexicographic, Gray, etc.) so that the user can control this.
May 28 2013
prev sibling parent reply "Peter Alexander" <peter.alexander.au gmail.com> writes:
On Monday, 27 May 2013 at 21:36:12 UTC, bearophile wrote:
 "pairwise" is a very useful lazy range similar to 
 cartesianProduct, but it yields only the ordered pairs, so they 
 cover only about half (a triangle) of the square matrix of the 
 possibilities.
This will be part of my combinatorics library, but is more general. pairWise is just a specific case of k-subsets (with k=2). By default, it currently provides the subsets in colexicographic order instead of lexicographic, but I intend to make the ordering a policy before I'm done.
May 27 2013
parent "bearophile" <bearophileHUGS lycos.com> writes:
Peter Alexander:

 This will be part of my combinatorics library, but is more 
 general. pairWise is just a specific case of k-subsets (with 
 k=2).
Yes, that's what's written a bit lower in my post, in the combinations() of Python. Bye, bearophile
May 28 2013