www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Preferred behavior of take() with ranges (value vs reference range)

reply Jon D <jond noreply.com> writes:
Just started looking at D, very promising!

One of the first programs I constructed involved infinite 
sequences. A design question  that showed up is whether to 
construct the range as a struct/value, or class/reference. It 
appears that structs/values are more the norm, but there are 
exceptions, notably refRange. I'm wondering if there are any 
community best practices or guidelines in this area.

One key difference is the behavior of take(). If the range is a 
value/struct, take() does not consume elements. If it's a 
ref/class, it does consume elements. From a consistency 
perspective, it'd seem useful if the behavior was consistent as 
much as possible.

Here's an example of the behavior differences below. It uses 
refRange, but same behavior occurs if the range is created as a 
class rather than a struct.

import std.range;
import std.algorithm;

void main() {
     auto fib1 = recurrence!((a,n) => a[n-1] + a[n-2])(1, 1);
     auto fib2 = recurrence!((a,n) => a[n-1] + a[n-2])(1, 1);
     auto fib3 = refRange(&fib2);

     // Struct/value based range - take() does not consume elements
     assert(fib1.take(7).equal([1, 1, 2, 3, 5, 8, 13]));
     assert(fib1.take(7).equal([1, 1, 2, 3, 5, 8, 13]));
     fib1.popFrontN(7);
     assert(fib1.take(7).equal([21, 34, 55, 89, 144, 233, 377]));

     // Reference range (fib3) - take() consumes elements
     assert(fib2.take(7).equal([1, 1, 2, 3, 5, 8, 13]));
     assert(fib3.take(7).equal([1, 1, 2, 3, 5, 8, 13]));
     assert(fib3.take(7).equal([21, 34, 55, 89, 144, 233, 377]));
     assert(fib2.take(7).equal([610, 987, 1597, 2584, 4181, 6765, 
10946]));
     assert(fib2.take(7).equal([610, 987, 1597, 2584, 4181, 6765, 
10946]));
}

--Jon
Nov 08 2015
parent reply TheFlyingFiddle <kurtyan student.chalmers.se> writes:
On Monday, 9 November 2015 at 02:14:58 UTC, Jon D wrote:

 Here's an example of the behavior differences below. It uses 
 refRange, but same behavior occurs if the range is created as a 
 class rather than a struct.
 --Jon


This is an artifact of struct based ranges being value types. 
When you use take the range get's copied into another structure 
that is also a range but limits the number of elements you take 
from that range.

Basically: take looks something like this: (simplified)

struct Take(Range)
{
    size_t count;
    Range  range;

     property ElementType!Range front() { return range.front; }
     property bool empty() { return count == 0 || range.empty; }
    void popFront() { count--; range.popFront; }
}

Code like this:

auto fib1 = ...

//Here fib1 get's copied into first5.
auto first5 = Take(5, fib);

So later when you perform actions on first5 you no longer take 
any action on fib1 but instead take action on the copied range 
inside of first5. Hence you don't see any consumption of fib1's 
elements.

However when you use a refRange / a class the Take range will 
take a reference / pointer to the actual range. So now your no 
longer working a copy of the range but on the range itself. As 
you reuse the same range you will see that consumption has 
occured.

If you want a more indepth explanation there were two talks at 
Dconf this year that (in part) discussed this topic. 
(https://www.youtube.com/watch?v=A8Btr8TPJ8c, 
https://www.youtube.com/watch?v=QdMdH7WX2ew&list=PLEDeq48KhndP-mlE-0Bfb_qPIMA4RrrKo&index=14)
Nov 08 2015
parent Jon D <jond noreply.com> writes:
On Monday, 9 November 2015 at 02:44:48 UTC, TheFlyingFiddle wrote:

 On Monday, 9 November 2015 at 02:14:58 UTC, Jon D wrote:

 Here's an example of the behavior differences below. It uses 
 refRange, but same behavior occurs if the range is created as 
 a class rather than a struct.
 --Jon


 This is an artifact of struct based ranges being value types. 
 When you use take the range get's copied into another structure 
 that is also a range but limits the number of elements you take 
 from that range.

 ...

 If you want a more indepth explanation there were two talks at 
 Dconf this year that (in part) discussed this topic. 
 (https://www.youtube.com/watch?v=A8Btr8TPJ8c, 
 https://www.youtube.com/watch?v=QdMdH7WX2ew&list=PLEDeq48KhndP-mlE-0Bfb_qPIMA4RrrKo&index=14)


Thanks for the quick reply. The two videos were very helpful. I 
understood what was happening underneath (mostly), but the videos 
made it clear there are a number of open questions regarding 
reference and value ranges and how best to use them.
Nov 08 2015