Bug 12007 – cartesianProduct doesn't work with ranges of immutables
Status
RESOLVED
Resolution
FIXED
Severity
normal
Priority
P2
Component
phobos
Product
D
Version
D2
Platform
All
OS
All
Creation time
2014-01-26T23:19:00Z
Last change time
2014-07-10T21:37:18Z
Assigned to
nobody
Creator
camille.brugel
Comments
Comment #0 by camille.brugel — 2014-01-26T23:19:25Z
The following code does not compile because Zip cannot modify the second tuple's member since it is immutable :
import std.algorithm;
import std.stdio;
void main()
{
immutable int[] A = [1,2,3];
immutable int[] B = [4,5,6];
auto AB = cartesianProduct(A,B);
writeln(AB);
}
The same thing appends here :
import std.stdio;
import std.range;
void main() {
writeln(zip([1,2,4,3], take(Repeat!(immutable(int))(2), 4)));
}
Is this a normal behaviour ?
Comment #1 by camille.brugel — 2014-01-26T23:27:21Z
The compiler message :
/usr/include/dmd/phobos/std/range.d(4199): Error: cannot modify struct result._ranges_field_1 Take!(Repeat!(immutable(int))) with immutable members
/usr/include/dmd/phobos/std/range.d(4503): Error: template instance std.range.Zip!(int[], Take!(Repeat!(immutable(int)))) error instantiating
test.d(8): instantiated from here: zip!(int[], Take!(Repeat!(immutable(int))))
test.d(8): Error: template instance std.range.zip!(int[], Take!(Repeat!(immutable(int)))) error instantiating
Comment #2 by camille.brugel — 2014-01-27T01:06:27Z
I found an ugly workaround for finite ranges (using cycle([a]) instead of repeat(a)) :
import std.algorithm;
import std.range;
import std.stdio;
auto myCartesianProduct(R1, R2)(R1 range1, R2 range2)
{
static if (isInfinite!R1 && isInfinite!R2)
{
static if (isForwardRange!R1 && isForwardRange!R2)
{
// This algorithm traverses the cartesian product by alternately
// covering the right and bottom edges of an increasing square area
// over the infinite table of combinations. This schedule allows us
// to require only forward ranges.
return zip(sequence!"n"(cast(size_t)0), range1.save, range2.save,
repeat(range1), repeat(range2))
.map!(function(a) => chain(
zip(repeat(a[1]), take(a[4].save, a[0])),
zip(take(a[3].save, a[0]+1), repeat(a[2]))
))()
.joiner();
}
else static assert(0, "cartesianProduct of infinite ranges requires "~
"forward ranges");
}
else static if (isInputRange!R2 && isForwardRange!R1 && !isInfinite!R1)
{
return joiner(map!((ElementType!R2 a) => zip(range1.save, cycle([a])))
(range2));
}
else static if (isInputRange!R1 && isForwardRange!R2 && !isInfinite!R2)
{
return joiner(map!((ElementType!R1 a) => zip(cycle([a]), range2.save))
(range1));
}
else static assert(0, "cartesianProduct involving finite ranges must "~
"have at least one finite forward range");
}
void main()
{
immutable int[] A = [1,2,3];
immutable int[] B = [4,5,6];
auto AB = myCartesianProduct(A,B);
writeln(AB);
}
Comment #3 by monarchdodra — 2014-01-28T03:39:53Z
Changing name: The problem isn't "immutable ranges" (which technically aren't even ranges btw), but having ranges of immutable.
The problem mainly lies in a combination `Repeat`, the `isForwardRange` trait, and `Zip`
The problem is that while `Repeat!(immutable(int))` *is* saveable, the type is not *assignable*. This could be partially fixed inside Repeat for objects that are "CompatibleUnqual".
It also sparks the questions of:
Should saveable ranges necessarily be assignable?
Now, with that said, zip makes an assignment in its save, when I'm pretty sure it could simply do construction (but this is a more of a generic issue actually).
In any case, *both* should be solvable pretty easily.
Comment #6 by bearophile_hugs — 2014-02-26T13:25:31Z
(In reply to comment #5)
> Commits pushed to master at https://github.com/D-Programming-Language/phobos
>
> https://github.com/D-Programming-Language/phobos/commit/301b42f0de6444db0e03067bbe4f899a41ba4fb2
> Fix issue 12007 - cartesianProduct does'nt work with ranges of immutables
After re-compiling Phobos, if I try to compile this:
void main() {
import std.algorithm: cartesianProduct;
auto s = "123456789"d;
foreach (p; cartesianProduct(s, s)) {}
}
I see the errors:
...\dmd2\src\phobos\std\algorithm.d-mixin-3643(3655,17): Error: cannot modify struct this._current Zip!(immutable(dchar)[], Repeat!(immutable(dchar))) with immutable members
...\dmd2\src\phobos\std\algorithm.d(3652,17): Error: cannot modify struct copy._current Zip!(immutable(dchar)[], Repeat!(immutable(dchar))) with immutable members
...\dmd2\src\phobos\std\algorithm.d(12624,22): Error: template instance std.algorithm.joiner!(MapResult!(__lambda3, immutable(dchar)[])) error instantiating
test.d(4,33): instantiated from here: cartesianProduct!(immutable(dchar)[], immutable(dchar)[])
test.d(4,33): Error: template instance std.algorithm.cartesianProduct!(immutable(dchar)[], immutable(dchar)[]) error instantiating
Perhaps I am doing something wrong, or I have a wrong Phobos?
Comment #7 by github-bugzilla — 2014-02-26T13:31:36Z
(In reply to comment #6)
> Perhaps I am doing something wrong, or I have a wrong Phobos?
It was a 2-part fix. The first was just a behavioral improvement for Zip, related to this issue, but didn't actually fix it. The "core" fix was just merged.
It should be working fine now (your code works fine for me). You can try it again now.
Comment #9 by bearophile_hugs — 2014-02-26T14:55:35Z
(In reply to comment #8)
> It should be working fine now (your code works fine for me). You can try it
> again now.
Unfortunately I am still seeing problems:
void main() {
import std.algorithm: cartesianProduct;
auto s = "123456789"d;
foreach (p; cartesianProduct(s, s, s)) {}
}
It gives me:
...\dmd2\src\phobos\std\algorithm.d-mixin-3643(3655,17): Error: cannot modify struct this._current Zip!(immutable(dchar)[], Repeat!(Tuple!(immutable(dchar), immutable(dchar)))) with immutable members
...\dmd2\src\phobos\std\algorithm.d(3652,17): Error: cannot modify struct copy._current Zip!(immutable(dchar)[], Repeat!(Tuple!(immutable(dchar), immutable(dchar)))) with immutable members
...\dmd2\src\phobos\std\algorithm.d(12624,22): Error: template instance std.algorithm.joiner!(MapResult!(__lambda3, Result)) error instantiating
...\dmd2\src\phobos\std\algorithm.d(12843,25): instantiated from here: cartesianProduct!(immutable(dchar)[], Result)
test.d(4,33): instantiated from here: cartesianProduct!(immutable(dchar)[], immutable(dchar)[], immutable(dchar)[])
...\dmd2\src\phobos\std\algorithm.d(12843,25): Error: template instance std.algorithm.cartesianProduct!(immutable(dchar)[], Result) error instantiating
test.d(4,33): instantiated from here: cartesianProduct!(immutable(dchar)[], immutable(dchar)[], immutable(dchar)[])
test.d(4,33): Error: template instance std.algorithm.cartesianProduct!(immutable(dchar)[], immutable(dchar)[], immutable(dchar)[]) error instantiating
(By the way, in my opinion the most important fix for cartesianProduct is to correct the order of its output. This is in another bug report.)
Comment #10 by monarchdodra — 2014-02-26T22:42:49Z
(In reply to comment #9)
> (In reply to comment #8)
>
> > It should be working fine now (your code works fine for me). You can try it
> > again now.
>
> Unfortunately I am still seeing problems:
>
> void main() {
> import std.algorithm: cartesianProduct;
> auto s = "123456789"d;
> foreach (p; cartesianProduct(s, s, s)) {}
> }
Indeed. I'll investigate.
Comment #11 by bearophile_hugs — 2014-06-20T21:15:52Z
*** Issue 10613 has been marked as a duplicate of this issue. ***
Comment #12 by bearophile_hugs — 2014-07-10T21:37:18Z