www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Ranges and Take

reply Jacob <noreply noreply.com> writes:
Currently some implementations rely on the struct Take from 
std.range to obtain certain functionality. I think this is a bit 
flawed, as it isn't generic enough. As such you end being locked 
to this "Take" structure. Which means you can't define your own 
implementation if needed.


https://github.com/dlang/phobos/blob/v2.071.2/std/container/dlist.d#L649


It is used here in DList in "linearRemove". There is a function 
"tail" which implements getting a range for the last few 
elements. But it is a bit inefficient as it first has to go 
through every single element from the front. At least in the case 
of a linked list. So maybe I want to implement my own "TailTake", 
that now means defining a new overload for "linearRemove" in 
DList. Then not only that there are already other functions in 
std.range that do define their on constructs, "takeOne()" for 
example does this. So that function can't be used with DList, and 
so forth.
Oct 04 2016
parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tuesday, October 04, 2016 14:22:51 Jacob via Digitalmars-d wrote:

 Currently some implementations rely on the struct Take from
 std.range to obtain certain functionality. I think this is a bit
 flawed, as it isn't generic enough. As such you end being locked
 to this "Take" structure. Which means you can't define your own
 implementation if needed.


 https://github.com/dlang/phobos/blob/v2.071.2/std/container/dlist.d#L649


 It is used here in DList in "linearRemove". There is a function
 "tail" which implements getting a range for the last few
 elements. But it is a bit inefficient as it first has to go
 through every single element from the front. At least in the case
 of a linked list. So maybe I want to implement my own "TailTake",
 that now means defining a new overload for "linearRemove" in
 DList. Then not only that there are already other functions in
 std.range that do define their on constructs, "takeOne()" for
 example does this. So that function can't be used with DList, and
 so forth.


The problem is that the range type has to be known for the *remove functions
to work. It needs to either be the original range or one that wraps the
original range in a known way. If it were an arbitrary range, there would be
no way to know which elements in the range corresponded to which elements in
the container - or whether the elements in the range had anything to do with
the container at all. It really doesn't work for the *remove functions to
take arbitrary ranges, even if they wrap the original range from the
container.

There needs to be a standard list of ranges that the *remove functions know
about and know how to handle, and the types that come from the take*
functions are the obvious choice. It may be that we need additional take*
functions for specific cases that aren't currently covered, but it really
isn't going to work to try and accept arbitrary ranges. That's actually part
of why we need better *remove functions that don't use ranges at all. This
is one of the few areas where ranges really don't work as well as iterators.

But as to a take* function that takes from the end, I don't see how we could
do that with the current range API - at least not and get a range out of it.
If you have a random access range, then either it supports slicing (in which
case you can just slice it), or it would be pretty trivial to create a
version of take that did the slicing for you (though really, that's an
argument for requiring that random access ranges just support slicing). So,
random access ranges really _should_ work right now without needing any
special take* functions. It's bidirectional ranges that would need some sort
of takeBack or takeTail. The problem is that while it would be trivial
enough to indicate that popBack only has n elements to pop off, for takeTail
to actually result in a range, it would need to give you access to the first
element in that range, and it can't do that, because the underlying range
isn't random access. And there's no such thing as a range that only has
back/popBack and not front/popFront.

So, what we'd end up with would be some sort of struct that wasn't actually
a range that the *remove functions recognized but which would be pretty much
useless outside of that, because it wouldn't be an actual range.

An alternative would be a *remove function that was supposed to specifically
remove elements that were at the end of the range, and it took an argument
for the number of elements. But that's not altogether pretty either.

Really, this is not a pretty problem. Using take* like we do now was the
best that we came up with to make it so that we didn't have to remove every
element in the range from the container, but it requires declaring multiple
*remove functions for each of the different versions of take*, and it's not
exactly pretty. But no one has come up with a better solution yet. The
"cursors" that Steven uses in dcollections might solve the problem, because
they become range/iterator hybrids, but Andrei is against using them in
Phobos. I'm not very familiar with their details though.

So, a better solution would definitely be great, but I don't see how it
could possibly work for a container's *remove function to accept arbitrary
ranges even if they wrap a range that originates from the container.

- Jonathan M Davis
Oct 04 2016
parent reply Jacob <noreply noreply.com> writes:
Having access to iterators would solve the problem here I think. 
But everything is ranges and that wouldn't entirely fit. For a 
linked list though, you can create a range from a single 
iterator. The implementation of DList's Range is pretty much two 
iterators. Oh well, have to implement my own anyways I guess, 
since DList uses the garbage collector.
Oct 04 2016
parent reply Jonathan M Davis via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Wednesday, October 05, 2016 00:10:39 Jacob via Digitalmars-d wrote:

 Having access to iterators would solve the problem here I think.
 But everything is ranges and that wouldn't entirely fit. For a
 linked list though, you can create a range from a single
 iterator. The implementation of DList's Range is pretty much two
 iterators. Oh well, have to implement my own anyways I guess,
 since DList uses the garbage collector.


A replacement for std.container is in the works, but who knows when that
will be done (or whether the result will really be what you want anyway). In
the interim, I'd recommend checking out

http://code.dlang.org/packages/emsi_containers

- Jonathan M Davis
Oct 04 2016
parent Jacob <noreply noreply.com> writes:
On Wednesday, 5 October 2016 at 02:16:57 UTC, Jonathan M Davis 
wrote:

 On Wednesday, October 05, 2016 00:10:39 Jacob via Digitalmars-d 
 wrote:

 Having access to iterators would solve the problem here I 
 think. But everything is ranges and that wouldn't entirely 
 fit. For a linked list though, you can create a range from a 
 single iterator. The implementation of DList's Range is pretty 
 much two iterators. Oh well, have to implement my own anyways 
 I guess, since DList uses the garbage collector.


 A replacement for std.container is in the works, but who knows 
 when that will be done (or whether the result will really be 
 what you want anyway). In the interim, I'd recommend checking 
 out

 http://code.dlang.org/packages/emsi_containers

 - Jonathan M Davis


Well I also need it to support noncopyable types. Which right now 
isInputRange (and other ranges) doesn't allow if "front" returns 
a reference. I found that it was already posted here a year or 
two back so I guess it isn't a priority to fix.
Oct 05 2016