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