www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Overriding iteration

reply Magnus Lie Hetland <magnus hetland.org> writes:
From what I understand, when you override iteration, you can either 
implement the basic range primitives, permitting foreach to 
destructively iterate over your object, or you can implement a custom 
method that's called, and that must perform the iteration. The 
destructiveness of the first option can, of course, be mitigated if you 
use a struct rather than a class, and make sure that anything that 
would be destroyed by popFront() is copied.

What I'm wondering is whether there is a way to do what Python does -- 
to construct/return an iterator (or, in this case, a range) that is 
used during the iteration, rather than the object itself?

I'm thinking about when you iterate directly over the object here. As 
far as I can see, the solution used in the std.container is to use 
opSlice() for this functionality. In other words, in order to iterate 
over container foo, you need to use foreach(e; foo[])? Is there no way 
to get this functionality directly (i.e., for foreach(e; foo))?

-- 
Magnus Lie Hetland
http://hetland.org
Mar 04 2011
next sibling parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Magnus Lie Hetland <magnus hetland.org> wrote:


 From what I understand, when you override iteration, you can either  
 implement the basic range primitives, permitting foreach to  
 destructively iterate over your object, or you can implement a custom  
 method that's called, and that must perform the iteration. The  
 destructiveness of the first option can, of course, be mitigated if you  
 use a struct rather than a class, and make sure that anything that would  
 be destroyed by popFront() is copied.

 What I'm wondering is whether there is a way to do what Python does --  
 to construct/return an iterator (or, in this case, a range) that is used  
 during the iteration, rather than the object itself?

 I'm thinking about when you iterate directly over the object here. As  
 far as I can see, the solution used in the std.container is to use  
 opSlice() for this functionality. In other words, in order to iterate  
 over container foo, you need to use foreach(e; foo[])? Is there no way  
 to get this functionality directly (i.e., for foreach(e; foo))?


foreach ( e; foo ) {}
Should work. I believe there is a bug already filed on it not working.

-- 
Simen
Mar 04 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
Simen kjaeraas <simen.kjaras gmail.com> wrote:


 Magnus Lie Hetland <magnus hetland.org> wrote:


 From what I understand, when you override iteration, you can either  
 implement the basic range primitives, permitting foreach to  
 destructively iterate over your object, or you can implement a custom  
 method that's called, and that must perform the iteration. The  
 destructiveness of the first option can, of course, be mitigated if you  
 use a struct rather than a class, and make sure that anything that  
 would be destroyed by popFront() is copied.

 What I'm wondering is whether there is a way to do what Python does --  
 to construct/return an iterator (or, in this case, a range) that is  
 used during the iteration, rather than the object itself?

 I'm thinking about when you iterate directly over the object here. As  
 far as I can see, the solution used in the std.container is to use  
 opSlice() for this functionality. In other words, in order to iterate  
 over container foo, you need to use foreach(e; foo[])? Is there no way  
 to get this functionality directly (i.e., for foreach(e; foo))?


 foreach ( e; foo ) {}
 Should work. I believe there is a bug already filed on it not working.


Found it:
http://d.puremagic.com/issues/show_bug.cgi?id=5605

-- 
Simen
Mar 04 2011
parent Magnus Lie Hetland <magnus hetland.org> writes:
On 2011-03-04 17:46:39 +0100, Simen kjaeraas said:


 Simen kjaeraas <simen.kjaras gmail.com> wrote:


[snip]

 Found it:
 http://d.puremagic.com/issues/show_bug.cgi?id=5605


Oo -- nice :) (That it should work, that is; not that it doesn't ;)

-- 
Magnus Lie Hetland
http://hetland.org
Mar 04 2011
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 Mar 2011 11:29:08 -0500, Magnus Lie Hetland  
<magnus hetland.org> wrote:


 From what I understand, when you override iteration, you can either  
 implement the basic range primitives, permitting foreach to  
 destructively iterate over your object, or you can implement a custom  
 method that's called, and that must perform the iteration. The  
 destructiveness of the first option can, of course, be mitigated if you  
 use a struct rather than a class, and make sure that anything that would  
 be destroyed by popFront() is copied.

 What I'm wondering is whether there is a way to do what Python does --  
 to construct/return an iterator (or, in this case, a range) that is used  
 during the iteration, rather than the object itself?


That's exactly how to do it.


 I'm thinking about when you iterate directly over the object here. As  
 far as I can see, the solution used in the std.container is to use  
 opSlice() for this functionality. In other words, in order to iterate  
 over container foo, you need to use foreach(e; foo[])? Is there no way  
 to get this functionality directly (i.e., for foreach(e; foo))?


I believe someone has filed a bug for this, because TDPL has said this  
should be possible.

But with the current compiler, you can use opApply to achieve that  
behavior.

-Steve
Mar 04 2011
next sibling parent reply spir <denis.spir gmail.com> writes:
On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:

 On Fri, 04 Mar 2011 11:29:08 -0500, Magnus Lie Hetland <magnus hetland.org>
wrote:


 From what I understand, when you override iteration, you can either implement
 the basic range primitives, permitting foreach to destructively iterate over
 your object, or you can implement a custom method that's called, and that
 must perform the iteration. The destructiveness of the first option can, of
 course, be mitigated if you use a struct rather than a class, and make sure
 that anything that would be destroyed by popFront() is copied.

 What I'm wondering is whether there is a way to do what Python does -- to
 construct/return an iterator (or, in this case, a range) that is used during
 the iteration, rather than the object itself?


 That's exactly how to do it.


 I'm thinking about when you iterate directly over the object here. As far as
 I can see, the solution used in the std.container is to use opSlice() for
 this functionality. In other words, in order to iterate over container foo,
 you need to use foreach(e; foo[])? Is there no way to get this functionality
 directly (i.e., for foreach(e; foo))?


 I believe someone has filed a bug for this, because TDPL has said this should
 be possible.

 But with the current compiler, you can use opApply to achieve that behavior.


opApply should work but it is supposed to be slower.
Defining range primitives directly on the object/container cannot work as of 
now, unfortunately, because of a pair of bugs (conflicts in formatValue 
template definitions between struct/class on one hand and ranges on the other).

Denis
-- 
_________________
vita es estrany
spir.wikidot.com
Mar 04 2011
parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 04 Mar 2011 12:13:34 -0500, spir <denis.spir gmail.com> wrote:


 On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:

 But with the current compiler, you can use opApply to achieve that  
 behavior.


 opApply should work but it is supposed to be slower.


It depends on the application and aggregate you are trying to iterate.

If inlining is possible, ranges can be extremely fast.  However, there are  
certain applications that are better suited or only work with opApply:

  * iterating polymorphic types (i.e. classes or interfaces)
  * iterating non-linearly (e.g. iterating a tree)
  * iterating multiple items in foreach (i.e. foreach(i, v; arr) )

In addition, LDC is able to inline opApply delegates that are  
compiler-generated, making opApply pretty much as fast as a range  
iteration.  I hope some day dmd can do this too.


 Defining range primitives directly on the object/container cannot work  
 as of now, unfortunately, because of a pair of bugs (conflicts in  
 formatValue template definitions between struct/class on one hand and  
 ranges on the other).


It is not a good idea to define range primitives on a container.  This  
would mean that iterating the container destroys the data.  What you want  
is a range on the container, and to iterate that range.  Think of a range  
as a view of the data in the container.  Think of the container as the  
owner of the data.  A confusing aspect is that builtin arrays are often  
thought of as containers.  They are not containers, they are ranges.  The  
owner of the data is actually the GC.

-Steve
Mar 04 2011
prev sibling next sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, March 04, 2011 09:13:34 spir wrote:

 On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:

 On Fri, 04 Mar 2011 11:29:08 -0500, Magnus Lie Hetland <magnus hetland.org> 




wrote:

 From what I understand, when you override iteration, you can either
 implement the basic range primitives, permitting foreach to
 destructively iterate over your object, or you can implement a custom
 method that's called, and that must perform the iteration. The
 destructiveness of the first option can, of course, be mitigated if you
 use a struct rather than a class, and make sure that anything that
 would be destroyed by popFront() is copied.
 
 What I'm wondering is whether there is a way to do what Python does --
 to construct/return an iterator (or, in this case, a range) that is
 used during the iteration, rather than the object itself?


 
 That's exactly how to do it.
 

 I'm thinking about when you iterate directly over the object here. As
 far as I can see, the solution used in the std.container is to use
 opSlice() for this functionality. In other words, in order to iterate
 over container foo, you need to use foreach(e; foo[])? Is there no way
 to get this functionality directly (i.e., for foreach(e; foo))?


 
 I believe someone has filed a bug for this, because TDPL has said this
 should be possible.
 
 But with the current compiler, you can use opApply to achieve that
 behavior.


 
 opApply should work but it is supposed to be slower.
 Defining range primitives directly on the object/container cannot work as
 of now, unfortunately, because of a pair of bugs (conflicts in formatValue
 template definitions between struct/class on one hand and ranges on the
 other).


You don't _want_ range primitives directly on the container. That would mean 
that everything in your container goes away when you process it. Every 
popFront() call would be removing an element from your container. So, for 
insteance, you try and call find() on your container and everything before what 
you were looking isn't in the container anymore - and if it isn't there at all, 
you have an empty container. You _want_ to have a separate type which is a
slice 
of our container and has the range primitives.


Now, it could very well be that

foreach(v; container)

should be calling opSlice on the container, allowing you to feed the container 
to foreach directly instead of having to slice it yourself

foreach(v; container[])

but that's just syntactic sugar. You don't want to actually treat your
container 
like a range. Ranges should be slices of containers, not containers themselves.

- Jonathan M Davis
Mar 04 2011
parent Magnus Lie Hetland <magnus hetland.org> writes:
On 2011-03-04 19:06:34 +0100, Jonathan M Davis said:


 On Friday, March 04, 2011 09:13:34 spir wrote:

 On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:




[snip]

 opApply should work but it is supposed to be slower.
 Defining range primitives directly on the object/container cannot work as
 of now, unfortunately, because of a pair of bugs (conflicts in formatValue
 template definitions between struct/class on one hand and ranges on the
 other).


 
 You don't _want_ range primitives directly on the container. That would mean
 that everything in your container goes away when you process it.


That was the point of my original question, yes :) In TDPL, where 
Andrei discusses overloading foreach, he has two main examples -- one 
using opApply, and one using such a self-destructive container. I think 
(as I said in my post) that what saves that list is that it's a struct, 
so it's copied by the initial assignment of the foreach statement.


 You _want_ to have a separate type which is a slice of our container 
 and has the range primitives.


Exactly. That was what I was asking for.


 
 Now, it could very well be that
 
 foreach(v; container)
 
 should be calling opSlice on the container, allowing you to feed the container
 to foreach directly instead of having to slice it yourself
 
 foreach(v; container[])
 
 but that's just syntactic sugar.


Sure. And judging from the other responses (and from TDPL), the fact 
that this doesn't currently work is just a bug.


 You don't want to actually treat your container like a range. Ranges 
 should be slices of containers, not containers themselves.


Well, it would still be nice to have things be consistent -- and in 
order for the opSlice approach to be consistent with the opApply 
approach (so a client needn't know how iteration is implemented for a 
given container), it seems reasonable to me to have foreach directly 
run on a slice of your container (i.e., implicitly calling []). But as 
this seems to be the way it is (save for the current bug), I guess it's 
sort of a moot point.

I certainly agree with your point, though. In Python, too, iterators 
(i.e., ranges) and iterables (i.e., containers) are separate concepts. 
You can iterate over an iterable, and the loop then automatically 
extracts an iterator. As this is The Way to Go, it makes sense to me 
that it's automatic/implicit.

-- 
Magnus Lie Hetland
http://hetland.org
Mar 04 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 03/04/2011 07:06 PM, Jonathan M Davis wrote:

 On Friday, March 04, 2011 09:13:34 spir wrote:

 On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:

 On Fri, 04 Mar 2011 11:29:08 -0500, Magnus Lie Hetland<magnus hetland.org>




 wrote:

  From what I understand, when you override iteration, you can either
 implement the basic range primitives, permitting foreach to
 destructively iterate over your object, or you can implement a custom
 method that's called, and that must perform the iteration. The
 destructiveness of the first option can, of course, be mitigated if you
 use a struct rather than a class, and make sure that anything that
 would be destroyed by popFront() is copied.

 What I'm wondering is whether there is a way to do what Python does --
 to construct/return an iterator (or, in this case, a range) that is
 used during the iteration, rather than the object itself?


 That's exactly how to do it.


 I'm thinking about when you iterate directly over the object here. As
 far as I can see, the solution used in the std.container is to use
 opSlice() for this functionality. In other words, in order to iterate
 over container foo, you need to use foreach(e; foo[])? Is there no way
 to get this functionality directly (i.e., for foreach(e; foo))?


 I believe someone has filed a bug for this, because TDPL has said this
 should be possible.

 But with the current compiler, you can use opApply to achieve that
 behavior.


 opApply should work but it is supposed to be slower.
 Defining range primitives directly on the object/container cannot work as
 of now, unfortunately, because of a pair of bugs (conflicts in formatValue
 template definitions between struct/class on one hand and ranges on the
 other).


 You don't _want_ range primitives directly on the container. That would mean
 that everything in your container goes away when you process it. Every
 popFront() call would be removing an element from your container. So, for
 insteance, you try and call find() on your container and everything before what
 you were looking isn't in the container anymore - and if it isn't there at all,
 you have an empty container. You _want_ to have a separate type which is a
slice
 of our container and has the range primitives.


Certainly, as long as, on an array-like container, you implement popFront as
     this = this[1..$];
or
     this.elements = this.elements[1..$];
then, yes, iterating on it shrinks it. (Note this works only on array-like 
containers; how would you shrink a tree?) But I prefere using a private index 
an have popFront do:
     ++ this.index;

This is a more general iteration mechanism solution, based on current state of 
the object beeing iterated on. For many kinds of sequences, you needs state 
anyway. How else iterate over the sequence of multiples of 3, or squares of 
natural numbers?


 Now, it could very well be that

 foreach(v; container)

 should be calling opSlice on the container, allowing you to feed the container
 to foreach directly instead of having to slice it yourself

 foreach(v; container[])

 but that's just syntactic sugar. You don't want to actually treat your
container
 like a range. Ranges should be slices of containers, not containers themselves.


I agree slices should be an alternate iteration mechanism (as said in TDPL). 
But one cannot slice a tree that easily :-) (where's my chain saw?)

Denis
-- 
_________________
vita es estrany
spir.wikidot.com
Mar 04 2011
prev sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On Friday, March 04, 2011 13:30:39 spir wrote:

 On 03/04/2011 07:06 PM, Jonathan M Davis wrote:

 On Friday, March 04, 2011 09:13:34 spir wrote:

 On 03/04/2011 05:43 PM, Steven Schveighoffer wrote:

 On Fri, 04 Mar 2011 11:29:08 -0500, Magnus Lie
 Hetland<magnus hetland.org>




 
 wrote:

  From what I understand, when you override iteration, you can either
 
 implement the basic range primitives, permitting foreach to
 destructively iterate over your object, or you can implement a custom
 method that's called, and that must perform the iteration. The
 destructiveness of the first option can, of course, be mitigated if
 you use a struct rather than a class, and make sure that anything
 that would be destroyed by popFront() is copied.
 
 What I'm wondering is whether there is a way to do what Python does --
 to construct/return an iterator (or, in this case, a range) that is
 used during the iteration, rather than the object itself?


 
 That's exactly how to do it.
 

 I'm thinking about when you iterate directly over the object here. As
 far as I can see, the solution used in the std.container is to use
 opSlice() for this functionality. In other words, in order to iterate
 over container foo, you need to use foreach(e; foo[])? Is there no way
 to get this functionality directly (i.e., for foreach(e; foo))?


 
 I believe someone has filed a bug for this, because TDPL has said this
 should be possible.
 
 But with the current compiler, you can use opApply to achieve that
 behavior.


 
 opApply should work but it is supposed to be slower.
 Defining range primitives directly on the object/container cannot work
 as of now, unfortunately, because of a pair of bugs (conflicts in
 formatValue template definitions between struct/class on one hand and
 ranges on the other).


 
 You don't _want_ range primitives directly on the container. That would
 mean that everything in your container goes away when you process it.
 Every popFront() call would be removing an element from your container.
 So, for insteance, you try and call find() on your container and
 everything before what you were looking isn't in the container anymore -
 and if it isn't there at all, you have an empty container. You _want_ to
 have a separate type which is a slice of our container and has the range
 primitives.


 
 Certainly, as long as, on an array-like container, you implement popFront
 as this = this[1..$];
 or
      this.elements = this.elements[1..$];
 then, yes, iterating on it shrinks it. (Note this works only on array-like
 containers; how would you shrink a tree?) But I prefere using a private
 index an have popFront do:
      ++ this.index;
 
 This is a more general iteration mechanism solution, based on current state
 of the object beeing iterated on. For many kinds of sequences, you needs
 state anyway. How else iterate over the sequence of multiples of 3, or
 squares of natural numbers?
 

 Now, it could very well be that
 
 foreach(v; container)
 
 should be calling opSlice on the container, allowing you to feed the
 container to foreach directly instead of having to slice it yourself
 
 foreach(v; container[])
 
 but that's just syntactic sugar. You don't want to actually treat your
 container like a range. Ranges should be slices of containers, not
 containers themselves.


 
 I agree slices should be an alternate iteration mechanism (as said in
 TDPL). But one cannot slice a tree that easily :-) (where's my chain saw?)


??? Go take a look RedBlackTree. It's sliced. And it's based on the current 
state of the container. _All_ slices are based on the current state of the 
container. They're a view into that container. You need to not think too much 
about arrays when thinking about slices. They're not normal. As Steve likes to 
point out, they're not really containers. They're slices. It's more like the GC 
is their container. So, arrays are actually a pretty bad example when
containers 
and ranges. And ranges _are_  a general iteration mechanism. I don't know what 
you would think is not general about that.

- Jonathan M Davis
Mar 04 2011