I've been enjoying my time with D's ranges, but something is nagging at me: If the range is not random access, then how does one create a sub-view of that range?

Say I have a forward range (for example, an SList[]). I would like to create a new range containing only the first 5 elements of that old range. How can I do that?

I see no logical reason that prevents me from doing it, since C++ iterators can do it quite fine. (the C++ algorithms that work only on RA ranges is mostly for efficiency reasons). Not being able to do this would severely limit the amount of containers that can seamlessly merge with algorithms.

For example, I can't call splitter on an SList. Not sure if this is just "not currently supported", or just not possible...

Any thoughts?

> Say I have a forward range (for example, an SList[]). I would like to create a new range containing only the first 5 elements of that old range. How can I do that?
>

std.algorithm.take.

But I would generally avoid SList.

On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
> std.algorithm.take.
>
> But I would generally avoid SList.

Thanks, but isn't that kind of a crutch solution?

I mean:

1) It creates a new type, so any attempt to use it to modify an existing range becomes impossible:
void main()
{
  SList!int slist;
  foreach(i; iota(5,0,-1))
    slist.insertFront(i);

  sr1 = take(sr1, 2); //Nope, not gonna happen
  writeln(sr1);
}

2) The new range is defined as a fixed length from the beginning of the range, as opposed to start and finish points. If I were to insert new items into my Slist, the new range would just bump the top items out of its range.

3) This doesn't work for BidirectionalRanges: The resulting range is forward only. For the same reason, it is not possible to have a TakeLast for bidirectional ranges.

----
Doesn't D offer any approach to "grow" a range?

Tobias Pankrath:

> But I would generally avoid SList.

It's not good.

And in general linked lists are quite overrated. On modern CPUs it's not easy to find situations where a linked list is better than a dynamic array or a chunked array (that is a dynamic array of pointers to arrays. It's often used to implement deques, etc).


Regarding arrays, maybe a StableVector will be good to have in Phobos:
http://www.boost.org/doc/libs/1_50_0_beta1/doc/html/container/non_standard_containers.html#container.non_standard_containers.stable_vector

Bye,
bearophile

On Saturday, 30 June 2012 at 12:27:38 UTC, bearophile wrote:
> Tobias Pankrath:
>
>> But I would generally avoid SList.
>
> It's not good.
>
> And in general linked lists are quite overrated.
> ...
> Bye,
> bearophile

I appreciate the input, which I (mostly) agree with (I still love list's splice ability, which can be very powerful), but this isn't really what the question is about.

It's about getting generic algorithms to work with any generic range. Right now, they appear (to me) to heavily favor RA, even when they should theoretically support simple bidirectionality...

Those that do support directionality do it using "cheat" using take. For example:

void main()
{
  SList!int slist;
  foreach(i; iota(5,0,-1))
    slist.insertFront(i);

  auto rnge = slist[];
  auto fs = findSplit!("a == b")(rnge, [3]);

  writeln(fs[0]); // [1, 2]
  slist.insertAfter(take(rnge, 1), 25); //insert 25 between [1, 2]
  writeln(fs[0]); // [1, 25] !?  Should arguably be [1, 25, 2]
}

This, arguably, is not normal behavior. SList modeling forward ranges, ranges to the list should not be bounded by a fixed size.

And again, had my input been a BDList (if it existed), findSplit would have returned 3 forwardRanges, which is also arguably wrong.

On 30-Jun-12 15:35, Tobias Pankrath wrote:
>> Say I have a forward range (for example, an SList[]). I would like to
>> create a new range containing only the first 5 elements of that old
>> range. How can I do that?
>>
>
> std.algorithm.take.
>
> But I would generally avoid SList.

Indeed. I'd be hard pressed to devise realistic use case where it performs better.

That makes me think that a proper type people should be using is the unrolled list, that is a list of fixed-sized array chunks.

Or even chunked array like bearophile suggests.
-- 
Dmitry Olshansky

On 6/30/12 7:31 AM, monarch_dodra wrote:
> I've been enjoying my time with D's ranges, but something is nagging at
> me: If the range is not random access, then how does one create a
> sub-view of that range?

Use take or takeExactly.

> Say I have a forward range (for example, an SList[]). I would like to
> create a new range containing only the first 5 elements of that old
> range. How can I do that?

take(r, n) or takeExactly(r, n).

> I see no logical reason that prevents me from doing it, since C++
> iterators can do it quite fine.

Actually, not at all. Iterators are a lot worse off than ranges here.

C++'s std::forward_list (and generally any iterator-providing singly-linked list) only offers an iterator to the first element. (The "end" iterator is a wrapped null pointer. This is by definition of the structure - singly-linked lists don't track their last element.)

So if you were to to take 5 elements off a std::forward_list, you can't use lst.begin() and lst.begin() + 5 because there's no addition; you'd need to define a new iterator type that combines a forward iterator with an integer, and iterate using that. It's all painstaking revealing how much a range is better for such. This is because the range keeps together the iteration limits, whereas iterators insist on the fact that the iteration limits belong separately.

> (the C++ algorithms that work only on RA
> ranges is mostly for efficiency reasons). Not being able to do this
> would severely limit the amount of containers that can seamlessly merge
> with algorithms.
>
> For example, I can't call splitter on an SList. Not sure if this is just
> "not currently supported", or just not possible...
>
> Any thoughts?

It must be very well understood what the structural limits of singly-linked lists impose on their iteration. There's no way to take 5 elements off a SList and pretend that's pretty much the same as taking the whole list.

We could build a design for using splitter with SLists only if the element type of splitter's result is different from SList's native range.


Andrei

On 6/30/12 8:24 AM, monarch_dodra wrote:
> On Saturday, 30 June 2012 at 11:35:07 UTC, Tobias Pankrath wrote:
>> std.algorithm.take.
>>
>> But I would generally avoid SList.
>
> Thanks, but isn't that kind of a crutch solution?
>
> I mean:
>
> 1) It creates a new type, so any attempt to use it to modify an existing
> range becomes impossible:
> void main()
> {
> SList!int slist;
> foreach(i; iota(5,0,-1))
> slist.insertFront(i);
>
> sr1 = take(sr1, 2); //Nope, not gonna happen
> writeln(sr1);
> }

One can't expect that to happen more than suspending a law of physics. The state needed for iterating an entire slist is a pointer. The state needed for iterating at most n elements of an slist is a pointer plus and integer. They're just different notions.

> 2) The new range is defined as a fixed length from the beginning of the
> range, as opposed to start and finish points. If I were to insert new
> items into my Slist, the new range would just bump the top items out of
> its range.

SList's range is not defined by start and finish points. It's defined as the start point, and the finish point is implicit by use of a sentinel (the null pointer).

> 3) This doesn't work for BidirectionalRanges: The resulting range is
> forward only. For the same reason, it is not possible to have a TakeLast
> for bidirectional ranges.

Not sure I understand this, but when we get into the realm of bidir ranges, things get a fair amount better. How would TakeLast work?


Andrei

On 6/30/12 9:15 AM, Dmitry Olshansky wrote:
> On 30-Jun-12 15:35, Tobias Pankrath wrote:
>>> Say I have a forward range (for example, an SList[]). I would like to
>>> create a new range containing only the first 5 elements of that old
>>> range. How can I do that?
>>>
>>
>> std.algorithm.take.
>>
>> But I would generally avoid SList.
>
> Indeed. I'd be hard pressed to devise realistic use case where it
> performs better.

Singly-linked lists are frequently used with lock-free algorithms. Generally it's simplistic to compare slists with arrays as to "which performs better" because they have different primitives.

Andrei

On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu wrote:
>> 2) The new range is defined as a fixed length from the beginning of the
>> range, as opposed to start and finish points. If I were to insert new
>> items into my Slist, the new range would just bump the top items out of
>> its range.
>
> SList's range is not defined by start and finish points. It's defined as the start point, and the finish point is implicit by use of a sentinel (the null pointer).
Well, what about in the case of a BidirRange from a BDList? Surelly, it would be defined by a start and finish point?

Take, on the other hand, creates a range, which is defined by a start point, and a fixed length. Inserting elements into the middle of the original list would bump elements out of the "take range", which remains fixed sized.

On the other hand, had I manually shrunk my BDlistRange until it was 5 elements long, and then inserted elements into the midle of the list, it would cause my BDListRange to grow, and nothing to drop out of it.

On Saturday, 30 June 2012 at 14:22:06 UTC, Andrei Alexandrescu wrote:
> On 6/30/12 8:24 AM, monarch_dodra wrote:
>> 3) This doesn't work for BidirectionalRanges: The resulting range is
>> forward only. For the same reason, it is not possible to have a TakeLast
>> for bidirectional ranges.
>
> Not sure I understand this, but when we get into the realm of bidir ranges, things get a fair amount better. How would TakeLast work?
>
>
> Andrei

Well, if we forget Slist, and just focus on a standard BidirectionalRange, say comming from a DList. Things don't really get any better, because take still returns just a ForwardRange.

There is no way of doing, say:

BidirectionalRange aBD = ...;

//Create subrange...
//aBD = take(aBD, 5); //Error, wrong type
auto subrange = take(aBD, 5);

if(subrange.back == 5) //Error, subrange does not have a back method.
                       //...But that's strange, because aBD IS a bidiretinal range

Since the Take Range it is defined by a begining point and a length, there is no way it could give Bidir access.

----
I came to D after reading your talk on ranges, and I really liked (and am still enjoying) the concept. However, with C++, when you iterate over [First, Last), you are also creating a two new ranges: [First, Current) & [Current, Last). D doesn't provide that, it only provides a way to shrink the current range and create [Current, Last).

Using range, you don't get [First, Current). At best, you only get
a)A forward range only
b)A fixed size range
c)A range of another type