Hello there.

I seem to be having problems wrapping my head around how to use the ranges in the context of containers in phobos. Specifically, I can't seem to figure out how to remove an element from a linked list.

         foreach(cell; organism)
         {
            if(cell.x == x && cell.y == y)
            {
               organism.stableLinearRemove(cell);
               break;
            }
         }

mind.d(123): Error: function std.container.SList!(Cell).SList.linearRemove (Range r) is not callable using argument types (Cell)
mind.d(123): Error: cannot implicitly convert expression (cell) of type cell.Cell to Take!(Range)

I somehow get the feeling such a basic operation should just...work?

/Max

On Sunday, October 30, 2011 11:38:30 Max Wolter wrote:
> Hello there.
> 
> I seem to be having problems wrapping my head around how to use the ranges in the context of containers in phobos. Specifically, I can't seem to figure out how to remove an element from a linked list.
> 
>           foreach(cell; organism)
>           {
>              if(cell.x == x && cell.y == y)
>              {
>                 organism.stableLinearRemove(cell);
>                 break;
>              }
>           }
> 
> mind.d(123): Error: function
> std.container.SList!(Cell).SList.linearRemove (Range r) is not callable
> using argument types (Cell)
> mind.d(123): Error: cannot implicitly convert expression (cell) of type
> cell.Cell to Take!(Range)
> 
> I somehow get the feeling such a basic operation should just...work?

linearRemove (and stableLinearRemove) takes a _range_ not a value. cell is an element in the list, not a range over the list. The range that it takes must be either of type SList.Range or Take!(SList.Range). You get that range by slicing an SList. Take!(SList.Range) is for the case where you want only a portion of the beginning of a range rather than the whole range. Your example actually has a really simple solution:

auto found = find!((a){return a.x == x && a.y == y;})(organism[]);
organism.stableLinearRemove(take(found, 1));

It finds the element in the list that you're looking for, and then it passes a range with that one element to stableLinearRemove so that it'll remove it.

- Jonathan M Davis

On 10/30/2011 6:45 PM, Jonathan M Davis wrote:
> On Sunday, October 30, 2011 11:38:30 Max Wolter wrote:
>> Hello there.
>>
>> I seem to be having problems wrapping my head around how to use the
>> ranges in the context of containers in phobos. Specifically, I can't
>> seem to figure out how to remove an element from a linked list.
>>
>>            foreach(cell; organism)
>>            {
>>               if(cell.x == x&&  cell.y == y)
>>               {
>>                  organism.stableLinearRemove(cell);
>>                  break;
>>               }
>>            }
>>
>> mind.d(123): Error: function
>> std.container.SList!(Cell).SList.linearRemove (Range r) is not callable
>> using argument types (Cell)
>> mind.d(123): Error: cannot implicitly convert expression (cell) of type
>> cell.Cell to Take!(Range)
>>
>> I somehow get the feeling such a basic operation should just...work?
>
> linearRemove (and stableLinearRemove) takes a _range_ not a value. cell is an
> element in the list, not a range over the list. The range that it takes must
> be either of type SList.Range or Take!(SList.Range). You get that range by
> slicing an SList. Take!(SList.Range) is for the case where you want only a
> portion of the beginning of a range rather than the whole range. Your example
> actually has a really simple solution:
>
> auto found = find!((a){return a.x == x&&  a.y == y;})(organism[]);
> organism.stableLinearRemove(take(found, 1));
>
> It finds the element in the list that you're looking for, and then it passes a
> range with that one element to stableLinearRemove so that it'll remove it.
>
> - Jonathan M Davis

Hello there.

Thank you very much for the explanation.

However, while I really liked the concept of ranges in Andrei's book and a lot of it seems intuitive and faster than using iterators, I can't shake the feeling that in this case, it's just unnecessarily convoluted.

Maybe it's just the fact that the container library is still very basic, but I don't think I should go through such a complicated procedure to remove an known element from a list. It's just not a "very simple" or intuitive solution, which is something I came to love D for thus far.

/Max

On Sunday, October 30, 2011 20:53:02 Max Wolter wrote:
> Hello there.
> 
> Thank you very much for the explanation.
> 
> However, while I really liked the concept of ranges in Andrei's book and a lot of it seems intuitive and faster than using iterators, I can't shake the feeling that in this case, it's just unnecessarily convoluted.
> 
> Maybe it's just the fact that the container library is still very basic, but I don't think I should go through such a complicated procedure to remove an known element from a list. It's just not a "very simple" or intuitive solution, which is something I came to love D for thus far.

You would be doing exactly the same thing in C++ except that it would be with an iterator rather than a range. You would use find to find the iterator to the element that you wanted and then you'd pass that to the list's erase function. It is only more complicated in D in that you get a range which _starts_ with the element that you want (essentially, you get the iterator to that element plus the end iterator for the list), so if you want to remove only the first element, you take it from the front of the range. Other than that, it's the same as in C++. You can't remove an element from a list in C++ by giving that element to the list anymore than you can in D. In both cases, you need an iterator or a range.

So, in comparison to C++, there's no significant difference. Now, Java does have a remove function which will take an element and remove the first occurence of that element from a list, and we could theoretically add one, but why? It would just be duplicating the functionality that find already gives. Java doesn't use iterators the way the C++ does, and it doesn't have ranges, so it _can't_ have a find function the way that C++ and D do, but D can. And in some cases, find can do it more efficiently than your loop could have.

I grant you that if you're not used to using find like this in C++ (and far, far too many C++ programmers use loops instead of find - in part because pre- C++11, there were no lambdas and any time you need a custom comparison function, it's a pain to get one), then it's not immediately intuitive, but it's far more flexible and powerful than removing elements by giving the element to a remove function on the list. And if you really want to use a loop, then you still can. You just can't use foreach.

for(auto r = organism[]; !r.empty; r.popFront())
{
    if(r.front.x == x && r.front.y == y)
    {
        organism.stableLinearRemove(take(r, 1));
        break;
    }
}

but that's a lot more verbose than simply using find, and as I said, in at least some cases, find can be more efficient than simply looping, since it's optimized for finding elements.

- Jonathan M Davis

On 10/31/2011 5:28 AM, Jonathan M Davis wrote:


>
> So, in comparison to C++, there's no significant difference. Now, Java does have
> a remove function which will take an element and remove the first occurence of
> that element from a list, and we could theoretically add one, but why?

IMO, it's much more intuitive to say list.remove(item). It's the first thing a lot of people expect coming from a Java background, that's for sure. The first time I tried to use SList, being unfamiliar with ranges as I was, it took a while to figure out what I needed to do. IIRC, I had to post here to ask.

The problem is that you really have to understand ranges and the Phobos functions that manipulate them before you can begin to use containers. I think that's wrong. Ideally, containers should be usable without having to know about find and Take and whatever else. This isn't the first time this question has come up in the NG and I've got a feeling it won't be the last.

At the very least it would be nice to see something in the documentation tying std.algorithm and std.range together with std.container. Something to point the way for those to whom it isn't obvious.

On Monday, October 31, 2011 12:11:45 Mike Parker wrote:
> On 10/31/2011 5:28 AM, Jonathan M Davis wrote:
> > So, in comparison to C++, there's no significant difference. Now, Java does have a remove function which will take an element and remove the first occurence of that element from a list, and we could theoretically add one, but why?
> IMO, it's much more intuitive to say list.remove(item). It's the first thing a lot of people expect coming from a Java background, that's for sure. The first time I tried to use SList, being unfamiliar with ranges as I was, it took a while to figure out what I needed to do. IIRC, I had to post here to ask.
> 
> The problem is that you really have to understand ranges and the Phobos functions that manipulate them before you can begin to use containers. I think that's wrong. Ideally, containers should be usable without having to know about find and Take and whatever else. This isn't the first time this question has come up in the NG and I've got a feeling it won't be the last.
> 
> At the very least it would be nice to see something in the documentation tying std.algorithm and std.range together with std.container. Something to point the way for those to whom it isn't obvious.

I definitely agree that the documentation should be improved to at least give the basic example of using find with linearRemove. Adding something similar to C++'s remove_if which removes all elements which match a predicate could also be useful, but I don't at all agree that there should be a function which takes an element and removes the first element which is equal to it. find allows you to do that just fine, and such a remove function would simply be duplicating its functionality.

As for understanding ranges, it's definitely true that there needs to be more documentation and/or articles on them so that the concept can better communicated. That's a definite flaw in the current documentation. But there's a lot in Phobos which you're just not going to be able to use if you don't understand ranges, and the library would definitely be worse if it used them less, since they're such a powerful concept, so I think that the problem is the lack of communication on ranges, not the fact that ranges are used so heavily in Phobos.

- Jonathan M Davis

Jonathan M Davis wrote:

>  find allows
> you to do that just fine, and such a remove function would simply be
> duplicating its functionality.

But this thread serves as a proof that it is not obvious and something like
containers should be obvious to use. Deleting an element with a certain
value is a common task and should should not take
three function calls, with functions from three different modules.

> You would be doing exactly the same thing in C++ except that it would be with an iterator rather than a range. You would use find to find the iterator to the element that you wanted and then you'd pass that to the list's erase function.
I don't think we should refer to C++ as an benchmark for ease of use.

How do you delete every occurence of v? Not just the first one? Is this equally "easy" with find and take? I didn't find an easy way not envolving a loop within 10 Minutes by reading the documentation.

What do you think of an construct like this:

foreach(item, itemRange; container)
{
// itemRange is a range only containing item
// itemRange.length == 1 && itemRange.front == item
}

That would be analogous to foreach over array with an index. You might think that iterating explicity may not be elegant. But it is what people want to do and it should not be any harder than necessary.

--
Tobias

On 31.10.2011 11:16, Tobias Pankrath wrote:
> Jonathan M Davis wrote:
>
>>   find allows
>> you to do that just fine, and such a remove function would simply be
>> duplicating its functionality.
>
> But this thread serves as a proof that it is not obvious and something like
> containers should be obvious to use. Deleting an element with a certain
> value is a common task and should should not take
> three function calls, with functions from three different modules.
>
>> You would be doing exactly the same thing in C++ except that it would be
>> with an iterator rather than a range. You would use find to find the
>> iterator to the element that you wanted and then you'd pass that to the
>> list's erase function.
> I don't think we should refer to C++ as an benchmark for ease of use.
>
> How do you delete every occurence of v? Not just the first one? Is this
> equally "easy" with find and take? I didn't find an easy way not
> envolving a loop within 10 Minutes by reading the documentation.

It is, let's use remove from std.algorithm! ... though there is no overload of remove for forward ranges ... crap, worthy of bugzilla report. Or SList could be special enough to offer a built-in remove with predicate done in O(n).

However this should work( yet because of apparent bug in SList it doesn't). The bug is:
Line 1294 of std.container should be:
	 for (; !r.empty; r.popFront())
...
or it will remove the whole container.

Code:
import std.container, std.range;
import std.functional, std.algorithm, std.stdio;

void removeFromList(alias pred, T)(ref SList!T s)
{
	static if(is(typeof(pred) == string))
		alias unaryFun!pred Pred;
	else
		alias pred Pred;
	for(auto r=s[]; !r.empty; )
	{
		if(Pred(r.front))
		{
			r = s.linearRemove(take(r,1));
			continue;
		}
		else
			r.popFront();
	}
}

void main()
{
	SList!int list(20, 30, 40, 50, 60); // will work with stock Phobos if the first element % 20 != 0
	removeFromList!"a % 20 == 0"(list);
	writeln(list[]);
	
}

And more importantly, it still would be horribly slow O(N^2). Personally, because of that I'd prefer hand-rolled intrusive singly-linked list any time of day.

>
> What do you think of an construct like this:
>
> foreach(item, itemRange; container)
> {
> // itemRange is a range only containing item
> // itemRange.length == 1&&  itemRange.front == item
> }

>
> That would be analogous to foreach over array with an index. You might think
> that iterating explicity may not be elegant. But it is what people want to
> do and it should not be any harder than necessary.
>

You still can, just use plain range interface with empty/front/popFront.
for(auto r = list[]; !r.empty; r.popFront())
{
	...
}


-- 
Dmitry Olshansky

On Monday, October 31, 2011 13:16:11 Dmitry Olshansky wrote:
> On 31.10.2011 11:16, Tobias Pankrath wrote:
> > Jonathan M Davis wrote:
> >>   find allows
> >> 
> >> you to do that just fine, and such a remove function would simply be duplicating its functionality.
> > 
> > But this thread serves as a proof that it is not obvious and something
> > like containers should be obvious to use. Deleting an element with a
> > certain value is a common task and should should not take
> > three function calls, with functions from three different modules.
> > 
> >> You would be doing exactly the same thing in C++ except that it would
> >> be
> >> with an iterator rather than a range. You would use find to find the
> >> iterator to the element that you wanted and then you'd pass that to
> >> the
> >> list's erase function.
> > 
> > I don't think we should refer to C++ as an benchmark for ease of use.
> > 
> > How do you delete every occurence of v? Not just the first one? Is this equally "easy" with find and take? I didn't find an easy way not envolving a loop within 10 Minutes by reading the documentation.
> 
> It is, let's use remove from std.algorithm! ... though there is no overload of remove for forward ranges ... crap, worthy of bugzilla report.

Probably because it has to swap elements around, which requires a bidirectional range.

> Or SList could be special enough to offer a built-in remove with
> predicate done in O(n).

It would be valuable in general IMHO. We should add something similar to the STL's remove_if function on linked lists. The fact that std.algorith.remove must shuffle elements around instead of actually removing them (similar to what the STL does with its free function erase) just shows how it doesn't really work all that well. It can be done _much_ more efficiently by putting remove_if (or whatever we would call it) on the container. It's also less confusing, since std.algorithm.remove (and the STL's erase function) doesn't actually _anything_. You have to pass the returned range (or iterator in C++) to the container's linearRemove function (or erase in C++) to remove the elements, which is _highly_ confusing (but since iterators and ranges don't really know about their containers beyond the elements that they reference, it's the best that can be done with a free function).

For the case where you're searching for a specific element to remove though, I see no reason to add another function. That's what find is for (and given that we have lambdas, it's easy to use even in the case where you need a predicate other than ==), and if you really want to, you can iterate the range explicitly and pass the portion of the range to the container's remove function that you want to remove. The main problem with it is that we don't have proper examples, and we don't have enough documentation explaining ranges in general, so it's not immediately obvious to people how to properly use a container's remove function.

- Jonathan M Davis

On Sun, 30 Oct 2011 06:38:30 -0400, Max Wolter <awishformore@gmail.com> wrote:

> Hello there.
>
> I seem to be having problems wrapping my head around how to use the ranges in the context of containers in phobos. Specifically, I can't seem to figure out how to remove an element from a linked list.
>
>           foreach(cell; organism)
>           {
>              if(cell.x == x && cell.y == y)
>              {
>                 organism.stableLinearRemove(cell);
>                 break;
>              }
>           }
>
> mind.d(123): Error: function std.container.SList!(Cell).SList.linearRemove (Range r) is not callable using argument types (Cell)
> mind.d(123): Error: cannot implicitly convert expression (cell) of type cell.Cell to Take!(Range)
>
> I somehow get the feeling such a basic operation should just...work?

I offer an alternative collection library to std.container which has a simpler (IMO) interface and features.

There is specifically a feature for removal during iteration.  It would look like this:

foreach(ref doRemove, cell; &organism.purge)
{
   doRemove = cell.x == x && cell.y == y; // flag indicating the current element should be removed
   // note, not necessary to break here
   if(doRemove)
      break;
}

Note two things, removal during iteration is directly supported, meaning it does not derail the iteration; and removal during iteration is a quick operation (O(lg(n)) or better) in terms of the individual removal.

If you have a linked list, you can also do it the "range" way:

organism.remove(find!((a){return a.x == x && a.y == y;})(organism[]).begin);

begin is an accessor for a dcollections range that returns a reference (cursor) to the first element in the range.

Note also that dcollections' linked list is doubly-linked, so removal is O(1).

-Steve