www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - joiner: How to iterate over immutable ranges?

reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
Hi,

I am having trouble getting the iteration methods in 
std.algorithm.iteration to work on immutable data:


 import std.algorithm.iteration;
 import std.stdio;
 
 void main()
 {
 	string[][] cycles;
 	cycles ~= ["one", "two"];
 	cycles ~= ["three", "four"];
 	foreach (number; cycles.joiner) // This works.
 		writeln(number);
 
 	immutable(string[])[] icycles;
 	icycles ~= ["one", "two"];
 	icycles ~= ["three", "four"];
 	foreach (number; icycles.joiner)  // Should this work?
 		writeln(number);
 }


The error message is:

/d149/f840.d(15): Error: template std.algorithm.iteration.joiner 
cannot deduce function from argument types 
!()(immutable(string[])[]), candidates are:
/opt/compilers/dmd2/include/std/algorithm/iteration.d(1911):      
   std.algorithm.iteration.joiner(RoR, Separator)(RoR r, Separator 
sep) if (isInputRange!RoR && isInputRange!(ElementType!RoR) && 
isForwardRange!Separator && is(ElementType!Separator : 
ElementType!(ElementType!RoR)))
/opt/compilers/dmd2/include/std/algorithm/iteration.d(2194):      
   std.algorithm.iteration.joiner(RoR)(RoR r) if (isInputRange!RoR 
&& isInputRange!(ElementType!RoR))

I had expected this to work. What did I miss?

Thanks,
Bastiaan.
Feb 14 2016
parent reply Jonathan M Davis via Digitalmars-d-learn writes:
On Sunday, February 14, 2016 15:24:39 Bastiaan Veelo via Digitalmars-d-learn
wrote:

 Hi,

 I am having trouble getting the iteration methods in
 std.algorithm.iteration to work on immutable data:


 import std.algorithm.iteration;
 import std.stdio;

 void main()
 {
     string[][] cycles;
     cycles ~= ["one", "two"];
     cycles ~= ["three", "four"];
     foreach (number; cycles.joiner) // This works.
         writeln(number);

     immutable(string[])[] icycles;
     icycles ~= ["one", "two"];
     icycles ~= ["three", "four"];
     foreach (number; icycles.joiner)  // Should this work?
         writeln(number);
 }


 The error message is:

 /d149/f840.d(15): Error: template std.algorithm.iteration.joiner
 cannot deduce function from argument types
 !()(immutable(string[])[]), candidates are:
 /opt/compilers/dmd2/include/std/algorithm/iteration.d(1911):
    std.algorithm.iteration.joiner(RoR, Separator)(RoR r, Separator
 sep) if (isInputRange!RoR && isInputRange!(ElementType!RoR) &&
 isForwardRange!Separator && is(ElementType!Separator :
 ElementType!(ElementType!RoR)))
 /opt/compilers/dmd2/include/std/algorithm/iteration.d(2194):
    std.algorithm.iteration.joiner(RoR)(RoR r) if (isInputRange!RoR
 && isInputRange!(ElementType!RoR))

 I had expected this to work. What did I miss?


An immutable range fundamentally does not work. The same goes with const. In
fact, a type that's immutable is going to fail isInputRange precisely
because it can't possibly function as one. While empty and front may be
callable on an immutable range, depending on their exact signatures,
popFront cannot be, because it has to mutate the range in order to work.

Arrays do typically get sliced when they're passed to functions, and array
slices are tail-const (e.g. const(int[]) is sliced as const(int)[]), so
something like

immutable string foo = "hello world";
auto result = foo.startsWith("goodbye");

will compile. But that doesn't work with ranges in general. What you're
doing is probably failing, because icycle[] is immutable(string)[], which is
immutable(char[])[], and it can't iterate over the immutable(char[]). But
regardless, if you try and use immutable with ranges, even if it works in
some cases thanks to how arrays are treated, it's just going to end up
shooting you in the foot in the end. So, I'd advise that you not bother
trying to do much with const or immutable with ranges.

- Jonathan M Davis
Feb 14 2016
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Sunday, 14 February 2016 at 18:28:11 UTC, Jonathan M Davis 
wrote:


 An immutable range fundamentally does not work. The same goes 
 with const. In fact, a type that's immutable is going to fail 
 isInputRange precisely because it can't possibly function as 
 one. While empty and front may be callable on an immutable 
 range, depending on their exact signatures, popFront cannot be, 
 because it has to mutate the range in order to work.


Thanks. I didn't know that iterating a range means mutating its 
contents. I still don't quite get it, and it is probably because 
I don't fully understand ranges. I think what confuses me the 
most is their analogy to containers. It's no problem to iterate 
over a container of immutable data, but it is for a range.

I thought that joiner provided a contiguous view on distinct 
ranges, without needing to touch these. Is there another method 
to traverse a range of ranges without making copies or mutation?
Feb 14 2016
next sibling parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/14/2016 11:32 AM, Bastiaan Veelo wrote:


 Thanks. I didn't know that iterating a range means mutating its
 contents.


That's not the case: Just like an iterator, a range must maintain some 
state to know which item is next. What needs to be mutated is that 
iteration state.


 I still don't quite get it, and it is probably because I don't
 fully understand ranges. I think what confuses me the most is their
 analogy to containers.


Yes, that analogy is the wrong one (and D's slices (or dynamic arrays) 
don't help with that).


 It's no problem to iterate over a container of immutable data, but
 it is for a range.


Not true. You can iterate over immutable data. In fact, a string is 
nothing but a container of immutable characters yet we can iterate over it.


 I thought that joiner provided a contiguous view on distinct ranges,
 without needing to touch these. Is there another method to traverse a
 range of ranges without making copies or mutation?


Not without making copies but note that the copy that you need to make 
is just the slices (i.e. views into data), which consist of just a 
length and a pointer fields. If it's acceptable for you, the following 
code calls .save on the elements and it works:

import std.algorithm.iteration;
import std.stdio;
import std.array;    // <-- ADDED

void main()
{
     immutable(string[])[] icycles;
     icycles ~= ["one", "two"];
     icycles ~= ["three", "four"];
     foreach (number; icycles.map!(r => r.save).joiner)
         writeln(number);
}

Again, .save on an array is cheap. What will happen is that the original 
immutable arrays will be untouched but their proxies returned by .save 
will be consumed.

Ali
Feb 14 2016
parent reply Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 15 February 2016 at 01:14:10 UTC, Ali Çehreli wrote:

 On 02/14/2016 11:32 AM, Bastiaan Veelo wrote:

 If it's acceptable for you, the following code calls .save on 
 the elements and it works:

 import std.algorithm.iteration;
 import std.stdio;
 import std.array;    // <-- ADDED

 void main()
 {
     immutable(string[])[] icycles;
     icycles ~= ["one", "two"];
     icycles ~= ["three", "four"];
     foreach (number; icycles.map!(r => r.save).joiner)
         writeln(number);
 }

 Again, .save on an array is cheap. What will happen is that the 
 original immutable arrays will be untouched but their proxies 
 returned by .save will be consumed.


Great, thanks. I didn't even know about save... Its documentation 
is hidden quite well, because I still cannot find it. Seems it is 
about time I read the books.
Feb 15 2016
parent reply =?UTF-8?Q?Ali_=c3=87ehreli?= <acehreli yahoo.com> writes:
On 02/15/2016 06:25 AM, Bastiaan Veelo wrote:


 I didn't even know about save... Its documentation is hidden quite
 well, because I still cannot find it.


Heh. :) It is a part of the ForwardRange interface (more correctly, 
"concept"?). It looks like "the additional capability that one can save 
one's current position with the save primitive" under isForwardRange is 
its official documentation:

   http://dlang.org/phobos/std_range_primitives.html


 Seems it is about time I read the books.


Agreed. Ranges is a concept where a little bit of documentation up front 
makes the ideas very clear.

Ali
Feb 15 2016
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 15 February 2016 at 18:13:48 UTC, Ali Çehreli wrote:

 On 02/15/2016 06:25 AM, Bastiaan Veelo wrote:


 I didn't even know about save... Its documentation is hidden 
 quite
 well, because I still cannot find it.


 Heh. :) It is a part of the ForwardRange interface (more 
 correctly, "concept"?). It looks like "the additional 
 capability that one can save one's current position with the 
 save primitive" under isForwardRange is its official 
 documentation:

   http://dlang.org/phobos/std_range_primitives.html


Wow, thanks. I did search that page before, but that section 
didn't give an echo on my radar...
Feb 15 2016
prev sibling parent reply Mike Parker <aldacron gmail.com> writes:
On Sunday, 14 February 2016 at 19:32:31 UTC, Bastiaan Veelo wrote:


 Thanks. I didn't know that iterating a range means mutating its 
 contents. I still don't quite get it, and it is probably 
 because I don't fully understand ranges. I think what confuses 
 me the most is their analogy to containers. It's no problem to 
 iterate over a container of immutable data, but it is for a 
 range.



Maybe this [1] will help shed some light.

[1] https://www.packtpub.com/books/content/understanding-ranges
Feb 14 2016
parent Bastiaan Veelo <Bastiaan Veelo.net> writes:
On Monday, 15 February 2016 at 01:42:30 UTC, Mike Parker wrote:

 On Sunday, 14 February 2016 at 19:32:31 UTC, Bastiaan Veelo 
 wrote:

 Maybe this [1] will help shed some light.

 [1] https://www.packtpub.com/books/content/understanding-ranges


Good idea. I have your book, but it is very nice to have this 
particular chapter freely online.

Thanks,
Bastiaan.
Feb 15 2016