www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 12007] New: cartesianProduct does'nt work with immutable ranges

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007

           Summary: cartesianProduct does'nt work with immutable ranges
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: camille.brugel laposte.net



PST ---
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 ?

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 26 2014
next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007




PST ---
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

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 26 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007




PST ---
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);
}

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 27 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |monarchdodra gmail.com
            Summary|cartesianProduct does'nt    |cartesianProduct does'nt
                   |work with immutable ranges  |work with ranges of
                   |                            |immutables



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.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Jan 28 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007




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

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

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 20 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007




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

https://d.puremagic.com/issues/show_bug.cgi?id=12007

This makes a tweak to `Zip`'s `save`: Now, it *builds* a new `Zip` object
from the saved ranges, rather than assigning each range individually.

This gives 2 advantages:
1. Better support for `save` (which doesn't actaully guarantee assignability)
2. Avoids useless `opAssign` overhead

https://github.com/D-Programming-Language/phobos/commit/8d800e59ccec7b39f6bb55d088fc84f9e04b2a37


Fix issue 12007 - cartesianProduct doesn't work with ranges of immutable...

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc





 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?

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007




Commits pushed to master at https://github.com/D-Programming-Language/phobos

https://github.com/D-Programming-Language/phobos/commit/1cc6c6a1429174c06c9f082699bb28be4c18ad7e
Fix issue 12007 - cartesianProduct does'nt work with ranges of immutables

The fix consists in making Repeat!T assignable, even if T itself is not.

https://github.com/D-Programming-Language/phobos/commit/98d4c60840d3fb06c03d4b4e6993dc1a69344b50


Fix issue 12007 - cartesianProduct does'nt work with ranges of immutable...

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED





 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.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014
prev sibling next sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007







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

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014
prev sibling parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=12007


monarchdodra gmail.com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |






 

 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.

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Feb 26 2014