www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Cartesian product of immutable ranges

reply "matovitch" <camille.brugel laposte.net> writes:
I posted a question on stackoverflow about the cartesian product 
of immutable ranges :

http://stackoverflow.com/questions/21368501/cartesian-product-of-immutable-ranges

There are a lot of various thing I don't understand.

This code compiles and run :

import std.stdio;
import std.range;
import std.algorithm;

void main() {

     immutable int[] B = [ 1, 2, 3 ];
     int[] C = [ 4, 5, 6 ];
     auto BC = cartesianProduct(B, C);
     writeln(BC);
}

This one doesn't :

import std.stdio;
import std.range;
import std.algorithm;

void main() {

     int[] B = [ 1, 2, 3 ];
     immutable int[] C = [ 4, 5, 6 ];
     auto BC = cartesianProduct(B, C);
     writeln(BC);
}

And this one does :

import std.stdio;
import std.range;
import std.algorithm;

void main() {

     immutable int[] B = [ 1, 2, 3 ];
     immutable int[] C = [ 4, 5, 6 ];
     auto BC = zip(B, C);
     writeln(BC);
}

Here B and C aren't inputRange thought acording to the template 
constraint of zip there should be. How can it compiles ? How to 
compute the cartesian product of two immutable ranges ?
Jan 26 2014
parent reply "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
On Sunday, 26 January 2014 at 21:49:37 UTC, matovitch wrote:

 void main() {

     immutable int[] B = [ 1, 2, 3 ];
     immutable int[] C = [ 4, 5, 6 ];
     auto BC = zip(B, C);
     writeln(BC);
 }

 Here B and C aren't inputRange thought acording to the template 
 constraint of zip there should be. How can it compiles ?
B and C aren't, but B[] and C[] are. That's what's going on when you pass an array as function argument: a full slice is taken. See for yourself: void foo(R)(R r) { writeln(R.stringof); } foo(B); // will print immutable(int)[]
 How to compute the cartesian product of two immutable ranges ?
Short answer: with std.algorithm - you can't. Because internally it (Zip, actually) performs assignments, and you can't assign to immutable(T). Why?
Jan 26 2014
next sibling parent reply "matovitch" <camille.brugel laposte.net> writes:
On Sunday, 26 January 2014 at 22:19:47 UTC, Stanislav Blinov 
wrote:
 On Sunday, 26 January 2014 at 21:49:37 UTC, matovitch wrote:

 void main() {

    immutable int[] B = [ 1, 2, 3 ];
    immutable int[] C = [ 4, 5, 6 ];
    auto BC = zip(B, C);
    writeln(BC);
 }

 Here B and C aren't inputRange thought acording to the 
 template constraint of zip there should be. How can it 
 compiles ?
B and C aren't, but B[] and C[] are. That's what's going on when you pass an array as function argument: a full slice is taken. See for yourself: void foo(R)(R r) { writeln(R.stringof); } foo(B); // will print immutable(int)[]
You mean that two input ranges are created from the immutable arrays when I call the function ? Zip doesn't compiles while zip compile. :/ Here is the implementation of zip : auto zip(Ranges...)(Ranges ranges) if (Ranges.length && allSatisfy!(isInputRange, Ranges)) { return Zip!Ranges(ranges); }
Jan 26 2014
parent reply "Jakob Ovrum" <jakobovrum gmail.com> writes:
On Sunday, 26 January 2014 at 22:32:32 UTC, matovitch wrote:
 You mean that two input ranges are created from the immutable 
 arrays when I call the function ?

 Zip doesn't compiles while zip compile. :/
`Zip` must be explicitly instantiated, which allows you to attempt to instantiate it with head-immutable slices, which isn't allowed because head-immutable slices aren't input ranges due to a lack of working `popFront()`.
 Here is the implementation of zip :

 auto zip(Ranges...)(Ranges ranges)
     if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 {
     return Zip!Ranges(ranges);
 }
`zip` is a range constructor function. These are used to allow IFTI (Implicit Function Template Instantiation) to infer template arguments, so the user doesn't have to provide them explicitly. With IFTI, head-immutable and head-const are stripped from slice types, so even though you pass immutable(int[]), the parameter type is set to be immutable(int)[], i.e. an mutable slice of immutable integers. Only the latter is a valid input range.
Jan 26 2014
parent "matovitch" <camille.brugel laposte.net> writes:
On Sunday, 26 January 2014 at 22:52:56 UTC, Jakob Ovrum wrote:
 On Sunday, 26 January 2014 at 22:32:32 UTC, matovitch wrote:
 You mean that two input ranges are created from the immutable 
 arrays when I call the function ?

 Zip doesn't compiles while zip compile. :/
`Zip` must be explicitly instantiated, which allows you to attempt to instantiate it with head-immutable slices, which isn't allowed because head-immutable slices aren't input ranges due to a lack of working `popFront()`.
 Here is the implementation of zip :

 auto zip(Ranges...)(Ranges ranges)
    if (Ranges.length && allSatisfy!(isInputRange, Ranges))
 {
    return Zip!Ranges(ranges);
 }
`zip` is a range constructor function. These are used to allow IFTI (Implicit Function Template Instantiation) to infer template arguments, so the user doesn't have to provide them explicitly. With IFTI, head-immutable and head-const are stripped from slice types, so even though you pass immutable(int[]), the parameter type is set to be immutable(int)[], i.e. an mutable slice of immutable integers. Only the latter is a valid input range.
Thank you very much for these very clear explanations ! I am quite tired tonight and shouldn't have started to code in the first place anyway. ;-)
Jan 26 2014
prev sibling parent reply "matovitch" <camille.brugel laposte.net> writes:
On Sunday, 26 January 2014 at 22:19:47 UTC, Stanislav Blinov 
wrote:
 On Sunday, 26 January 2014 at 21:49:37 UTC, matovitch wrote:

 Short answer: with std.algorithm - you can't. Because internally
 it (Zip, actually) performs assignments, and you can't assign to
 immutable(T).

 Why?
Here is the problem... import std.stdio; import std.range; import std.algorithm; void main() { writeln(zip([1,2,4,3], take(Repeat!(immutable(int))(2), 4))); } With the current implementation the second order immutable should be stripped...
Jan 26 2014
parent "Stanislav Blinov" <stanislav.blinov gmail.com> writes:
You might want to consider submitting a bug report on account of 
cartesianProduct() not being able to deal with ranges of 
immutable elements. The worst that can happen is that you'd get a 
real expert's explanation on why it's not a bug. But who knows, 
perhaps it is :)
Jan 26 2014