On Wed, 23 Feb 2005 21:02:15 -0500, Ben Hinkle <ben.hinkle@gmail.com> wrote:
> "Regan Heath" <regan@netwin.co.nz> wrote in message
> news:opsmof4pem23k2f5@ally...
>> On Wed, 23 Feb 2005 19:53:27 -0500, Ben Hinkle <ben.hinkle@gmail.com>
>> wrote:
>>> "John Demme" <me@teqdruid.com> wrote in message
>>> news:cvj6rk$2e8n$1@digitaldaemon.com...
>>>> Ben Hinkle wrote:
>>>>>   List!(int) x;
>>>>>   ...
>>>>>   foreach(int item; x.backwards) {
>>>>>   ....
>>>>>   }
>>>>> to iterate backwards over a list. The "reverse" property of List works
>>>>> just like the array reverse property and reverses the list items
>>>>> in-place.
>>>>
>>>> Sounds like you want the List template to have a backwards method that
>>>> returns a class that will iterate over the original list backwards.
>>>> Seems
>>>> like a simple enough thing to do.
>>>>
>>>> Or do I misunderstand?
>>>>
>>>> John
>>>
>>> Yeah - that's what I did. I was describing how I implemented a similar
>>> feature for non-arrays as another data point in the discussion.
>>
>> It seems to me that it doesn't necessarily need to be a different class,
>> it could be another copy of the same class, containing the same info,
>> backwards.
>>
>> Of course, sometimes a different class is preferrable.
>>
>> Regan
>
> Two points:
> 1) it's actually a struct so that no garbage is created by foreaching
> backwards. If I had to choose between writing a for loop that steps
> backwards and writing a foreach loop that generating garbage I'd choose
> writing the for loop - but that's me.

Yeah, this is what I was thinking about when I said that a different class (I meant to include struct) was preferrable sometimes.

> 2) a different type is needed because foreach on a regular List means
> forwards foreach and I decided that storing a flag as part of a general List just for backwards traversals wasn't worth the storage space.

You're probably right. Unless you were doing a lot of list reversals the common case would never need/use it.

I was thinking that the simplest solution is to go:

class List {
  List backwards() {
    List l = new List();
    foreach(Item i; this) {
      l.addStart(i);
    }
    return l;
  }
}

in other words, make a new list, put the items in it in reverse order, return that.

But, as you say, more garbage, less efficient.

> The actual implementation factors out the for loop into a function that the regular List calls with a step of +1 and the BackwardsList (or whatever name I used) calls with step -1.

Cunning, I'll have to have a look at that code at some stage.

Regan

In article <opsmoeedwu23k2f5@ally>, Regan Heath says...
>
>On Thu, 24 Feb 2005 00:13:19 +0000 (UTC), James Dunne <jdunne4@bradley.edu> wrote:
>> In article <opsmocl1lz23k2f5@ally>, Regan Heath says...
>>>
>>> Can't you go..
>>>
>>> array = listBox.selectedIndices().dup;
>>> foreach(Item i; array.reverse) {
>>> }
>>
>> Not for a class.  dup is a property of arrays.  The function
>> selectedIndices()
>> returns a class called SelectedIndexCollection which has opApply
>> overloaded.
>
>Ahh. ok. I see.
>
>Ok, in order to be symetrical with an array, should it have a reverse method i.e.
>
>c = listBox.selectedIndices().reverse;
>foreach(Item i; c) {
>}

What does a class want to reverse?  I know what you mean, but in a general sense, it's not very clear.

>
>Granted, a way to iterate backwards, or every 2nd,3rd,4th item .. without having to make a copy of the container would be useful and efficient.
>

Exactly: without having to make a copy.  foreachreverse would be implemented for arrays automatically, instead of having to use .dup .reverse.  It's an in-place reverse iteration and won't cost any more than a forward iteration.  There's really no reason not to have it.

A foreachreverse (or whatever the syntax would be) would look much clearer to the naked eye that you are in fact reverse iterating through a class/array/struct.

Regards,
James Dunne

In article <cvj669$2dtp$1@digitaldaemon.com>, Ben Hinkle says...
>
>It would be nice to get something like it. I remember this coming when I was working on the containers in MinTL and so my solution there was to have a property called "backwards" on the container like List that returned a private struct that only implemented foreach (or something like that - I actually can't remember exactly without going and looking it up). So basically the user types
>  List!(int) x;
>  ...
>  foreach(int item; x.backwards) {
>  ....
>  }
>to iterate backwards over a list. The "reverse" property of List works just like the array reverse property and reverses the list items in-place.
>

You were clear up to this point... You lost me on this next paragraph.

>I don't know if such a syntax would be a good idea in general. I suppose it depends on exactly how the type of x.backwards would work. Maybe it can have special behavior like "length" where it does magic things in different contexts (ironic that I'm saying this since I'm not a big fan of the magic length behavior).
>

I'm proposing a new set of opApply and foreach constructs to simply provide support for reverse iteration.  No special hacks need be introduced.  Keep it simple and sweet.

Regards,
James Dunne

On Thu, 24 Feb 2005 02:53:44 +0000 (UTC), James Dunne <jdunne4@bradley.edu> wrote:
> In article <opsmoeedwu23k2f5@ally>, Regan Heath says...
>>
>> On Thu, 24 Feb 2005 00:13:19 +0000 (UTC), James Dunne
>> <jdunne4@bradley.edu> wrote:
>>> In article <opsmocl1lz23k2f5@ally>, Regan Heath says...
>>>>
>>>> Can't you go..
>>>>
>>>> array = listBox.selectedIndices().dup;
>>>> foreach(Item i; array.reverse) {
>>>> }
>>>
>>> Not for a class.  dup is a property of arrays.  The function
>>> selectedIndices()
>>> returns a class called SelectedIndexCollection which has opApply
>>> overloaded.
>>
>> Ahh. ok. I see.
>>
>> Ok, in order to be symetrical with an array, should it have a reverse
>> method i.e.
>>
>> c = listBox.selectedIndices().reverse;
>> foreach(Item i; c) {
>> }
>
> What does a class want to reverse?  I know what you mean, but in a general sense, it's not very clear.

I wasn't trying to imply all classes need one, or even all containers.

Those classes that act as containers might want one, if it makes sense to reverse the contents of the container. eg. like it does for arrays, but not associative ones.

>> Granted, a way to iterate backwards, or every 2nd,3rd,4th item .. without
>> having to make a copy of the container would be useful and efficient.
>>
>
> Exactly: without having to make a copy.  foreachreverse would be implemented for
> arrays automatically, instead of having to use .dup .reverse.  It's an in-place
> reverse iteration and won't cost any more than a forward iteration.  There's
> really no reason not to have it.

I agree.

You can still hand code it with a for loop, assuming that is, that you can access the items with [] and you know the last index.

The idea behind foreach is to avoid having to code specifically for the container type. i.e. indexes, linklist etc. I think this, or similar idea, is required to achieve that goal.

> A foreachreverse (or whatever the syntax would be) would look much clearer to
> the naked eye that you are in fact reverse iterating through a
> class/array/struct.

foreach_r() maybe.

Does the term "foreach" imply any direction forward or backward? To me it doesn't. I realise it's used in other languages, the same as in D, so it has a commonly understood meaning.

I think the options are:

- leave foreach, invent a backwards term i.e. foreach_r.
- invent new terms, one for forward, one for backward.
- add the ability to specify the 'step' in foreach


Regan

>>I don't know if such a syntax would be a good idea in general. I suppose
>>it
>>depends on exactly how the type of x.backwards would work. Maybe it can
>>have
>>special behavior like "length" where it does magic things in different
>>contexts (ironic that I'm saying this since I'm not a big fan of the magic
>>length behavior).
>>
>
> I'm proposing a new set of opApply and foreach constructs to simply
> provide
> support for reverse iteration.  No special hacks need be introduced.  Keep
> it
> simple and sweet.

Yeah that might be best. I don't have a strong opinion about what the best answer would be. I was exploring a solution that didn't involve adding a keyword. A reverse foreach over associative arrays isn't needed because the order is random anyway so should AA's be foreachreverse-able? Maybe there's some solution involving adding a stepsize argument to the foreach and saying that negative step sizes are reverse traversals? eh, I don't know.

In article <opsmol1osx23k2f5@ally>, Regan Heath says...
>
>Does the term "foreach" imply any direction forward or backward? To me it doesn't. I realise it's used in other languages, the same as in D, so it has a commonly understood meaning.
>
>I think the options are:
>
>- leave foreach, invent a backwards term i.e. foreach_r.
>- invent new terms, one for forward, one for backward.
>- add the ability to specify the 'step' in foreach
>
>
>Regan

I agree with the options listed, and really they're not up to me to decide ;). On specifying the 'step' for the foreach, that doesn't seem especially useful unless it's either +1 or -1, which I'm sure is what your point was.  I'm just saying I don't see why anyone would use a container to foreach through on a specified interval bigger than one.

Maybe a punny syntax like "foreach" is short for forward-each, and we could have "backeach".  foreach to me seems to imply order, and is usually implemented as a forward iteration.  It would be clearer to specify new terms, one for forward, one for backward, but so much D code exists using 'foreach' and it'd be a pain to go thru and change all that.

It's wisest to keep 'foreach' and 'opApply' and just add new terms for the reverse. 'foreach_r' seems appealing to me.  opApply_r, on the other hand, does not.  The other functions opAdd_r, etc. are used to handle cases where the first argument is not the 'this' pointer of the class, not to "reversely add" something, whatever that means ;).  I'd suggest opApplyReverse in this case.

Regards,
James Dunne

In article <cvjgro$2odu$1@digitaldaemon.com>, Ben Hinkle says...
>
>>>I don't know if such a syntax would be a good idea in general. I suppose
>>>it
>>>depends on exactly how the type of x.backwards would work. Maybe it can
>>>have
>>>special behavior like "length" where it does magic things in different
>>>contexts (ironic that I'm saying this since I'm not a big fan of the magic
>>>length behavior).
>>>
>>
>> I'm proposing a new set of opApply and foreach constructs to simply
>> provide
>> support for reverse iteration.  No special hacks need be introduced.  Keep
>> it
>> simple and sweet.
>
>Yeah that might be best. I don't have a strong opinion about what the best answer would be. I was exploring a solution that didn't involve adding a keyword. A reverse foreach over associative arrays isn't needed because the order is random anyway so should AA's be foreachreverse-able? Maybe there's some solution involving adding a stepsize argument to the foreach and saying that negative step sizes are reverse traversals? eh, I don't know.
>

I understand what you were doing with MinTL and the .backwards property.  I'd like to try to accomplish it without any memory duplication or "garbage produced."  If that involves adding a new keyword to the language, that's fine with me!

You can't foreach on an AA by itself, you have to foreach on the .keys or the values properties of the AA, which are just regular arrays.

So if the foreach-reverse keyword is introduced, you'd reverse iterate on the keys or the values of the AA.

Of course, reverse iteration on the keys or values doesn't matter much, unless you want to reverse iterate through the SORTED keys or values, which DOES make sense. :)

Regards,
James Dunne

On Thu, 24 Feb 2005 03:41:02 +0000 (UTC), James Dunne <jdunne4@bradley.edu> wrote:
> In article <opsmol1osx23k2f5@ally>, Regan Heath says...
>>
>> Does the term "foreach" imply any direction forward or backward? To me it
>> doesn't. I realise it's used in other languages, the same as in D, so it
>> has a commonly understood meaning.
>>
>> I think the options are:
>>
>> - leave foreach, invent a backwards term i.e. foreach_r.
>> - invent new terms, one for forward, one for backward.
>> - add the ability to specify the 'step' in foreach
>>
>>
>> Regan
>
> I agree with the options listed, and really they're not up to me to decide ;).
> On specifying the 'step' for the foreach, that doesn't seem especially useful
> unless it's either +1 or -1, which I'm sure is what your point was.

Actually, I was being intentionally vague :)

> I'm just
> saying I don't see why anyone would use a container to foreach through on a
> specified interval bigger than one.

Isn't it the same reason someone would use a for loop with i+=2, or i-=2?

Of course in addition to the step you need some way to indicate where to start start, end, x.

That is, unless you assume -1 means start at the end, and +1 means start at the beginning and that no-one ever wants to start elsewhere.

I think the concept of direction and step can apply to arrays, linklists, and other types of containers, if so does that mean foreach should handle them?

> Maybe a punny syntax like "foreach" is short for forward-each

I thought it was "for each" as in "for each item in .."

> , and we could have
> "backeach".  foreach to me seems to imply order, and is usually implemented as a
> forward iteration.

I suspected that to others it might imply order.

> It would be clearer to specify new terms, one for forward,
> one for backward, but so much D code exists using 'foreach' and it'd be a pain
> to go thru and change all that.

That was sort of my conclusion also.

> It's wisest to keep 'foreach' and 'opApply' and just add new terms for the
> reverse. 'foreach_r' seems appealing to me.

Assuming there is no reason to want step then this option seems the best to me.

> opApply_r, on the other hand, does
> not.  The other functions opAdd_r, etc. are used to handle cases where the first
> argument is not the 'this' pointer of the class, not to "reversely add"
> something, whatever that means ;).  I'd suggest opApplyReverse in this case.

I didn't think about the naming of opApply.

Regan

In article <opsmooadap23k2f5@ally>, Regan Heath says...
>
>On Thu, 24 Feb 2005 03:41:02 +0000 (UTC), James Dunne <jdunne4@bradley.edu> wrote:
>> In article <opsmol1osx23k2f5@ally>, Regan Heath says...
>>>
>>> Does the term "foreach" imply any direction forward or backward? To me
>>> it
>>> doesn't. I realise it's used in other languages, the same as in D, so it
>>> has a commonly understood meaning.
>>>
>>> I think the options are:
>>>
>>> - leave foreach, invent a backwards term i.e. foreach_r.
>>> - invent new terms, one for forward, one for backward.
>>> - add the ability to specify the 'step' in foreach
>>>
>>>
>>> Regan
>>
>> I agree with the options listed, and really they're not up to me to
>> decide ;).
>> On specifying the 'step' for the foreach, that doesn't seem especially
>> useful
>> unless it's either +1 or -1, which I'm sure is what your point was.
>
>Actually, I was being intentionally vague :)
>
>> I'm just
>> saying I don't see why anyone would use a container to foreach through
>> on a
>> specified interval bigger than one.
>
>Isn't it the same reason someone would use a for loop with i+=2, or i-=2?
>

Not necessarily.  Foreach was created to iterate through lists.  for() was meant to give flexible looping ability.  If you want to skip indicies, use a regular for() loop.  Any well-implemented class that implements opApply (foreach support) should also implement opIndex to give access to individual elements.

Besides, adding a step, start, and end to the current foreach syntax has the possibility of breaking code as it stands now.  However, they could be optional arguments and not break anything, or they could be an optionally allowed syntax in addition to the "old (current) way".

>Of course in addition to the step you need some way to indicate where to start start, end, x.
>
>That is, unless you assume -1 means start at the end, and +1 means start at the beginning and that no-one ever wants to start elsewhere.
>
>I think the concept of direction and step can apply to arrays, linklists, and other types of containers, if so does that mean foreach should handle them?
>

If you can give me a legitimate example where you would *need* to skip elements on a constant step using foreach, then I'll agree with you.  I just can't think of any off-hand.

>> Maybe a punny syntax like "foreach" is short for forward-each
>
>I thought it was "for each" as in "for each item in .."
>

That's technically what it means, yes.  But I was just throwing in the pun of foreach breaking up as "forward" and "each" to allow a backeach meaning "back" and "each".  Just a dumb pun, don't worry about it ;)

>> , and we could have
>> "backeach".  foreach to me seems to imply order, and is usually
>> implemented as a
>> forward iteration.
>
>I suspected that to others it might imply order.
>

And it does.  When you foreach through a D array, you iterate forward through it.  It's just generally accepted that it has a forward order to it.  In other languages (e.g. PHP, Perl, C#) this is true as well.

>> It would be clearer to specify new terms, one for forward,
>> one for backward, but so much D code exists using 'foreach' and it'd be
>> a pain
>> to go thru and change all that.
>
>That was sort of my conclusion also.
>

Excellent!

>> It's wisest to keep 'foreach' and 'opApply' and just add new terms for
>> the
>> reverse. 'foreach_r' seems appealing to me.
>
>Assuming there is no reason to want step then this option seems the best to me.
>
>> opApply_r, on the other hand, does
>> not.  The other functions opAdd_r, etc. are used to handle cases where
>> the first
>> argument is not the 'this' pointer of the class, not to "reversely add"
>> something, whatever that means ;).  I'd suggest opApplyReverse in this
>> case.
>
>I didn't think about the naming of opApply.
>

I just threw it out there, since it goes hand-in-hand with foreach.  If we want to throw consistency and clarity out the window, opApply_r would be acceptable (and probably favorable to opApplyReverse).

Regards,
James Dunne

Wouldn't this serve for now at least?  Personally I think it is better than adding new keywords/operators to the language...

<code>
module andy.backwards.backwards;

import std.stdio;

template backwards(List, Delegate)
{
struct reverse_iterator
{
List list;

int opApply(Delegate dg)
{
return list.opApplyReverse(dg);
}
}

reverse_iterator backwards()
{
reverse_iterator r;
r.list = this;
return r;
}
}

class Foo
{
mixin backwards!(Foo, int delegate(inout int));

int opApply(int delegate(inout int) dg)
{
int result = 0;
for(int i = 0; i < 10; i++)
{
result = dg(i);
if(result)
break;
}
return result;
}

int opApplyReverse(int delegate(inout int) dg)
{
int result = 0;
for(int i = 9; i >= 0; i--)
{
result = dg(i);
if(result)
break;
}
return result;
}
}

void main(char[][] args)
{
Foo foo = new Foo();

foreach(int i; foo)
writefln(i);

foreach(int i; foo.backwards)
writefln(i);
}
</code>

Adding a reverse iterator to a class requires only a mixin and the definition of the iterator itself (called opApplyReverse here).  Calling the iterator requires only a .backwards on the end of the foreach expression.

You can replace the templated delegate type with a templated item type to make typing the mixins easier, but then you can't create different iterators (say with an accompanying index).

Hopefully with inlining and optomising this would be about as fast as normal foreaching?

In article <opsmojp1qc23k2f5@ally>, Regan Heath says...
>
>On Wed, 23 Feb 2005 21:02:15 -0500, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>> "Regan Heath" <regan@netwin.co.nz> wrote in message news:opsmof4pem23k2f5@ally...
>>> On Wed, 23 Feb 2005 19:53:27 -0500, Ben Hinkle <ben.hinkle@gmail.com> wrote:
>>>> "John Demme" <me@teqdruid.com> wrote in message news:cvj6rk$2e8n$1@digitaldaemon.com...
>>>>> Ben Hinkle wrote:
>>>>>>   List!(int) x;
>>>>>>   ...
>>>>>>   foreach(int item; x.backwards) {
>>>>>>   ....
>>>>>>   }
>>>>>> to iterate backwards over a list. The "reverse" property of List
>>>>>> works
>>>>>> just like the array reverse property and reverses the list items
>>>>>> in-place.
>>>>>
>>>>> Sounds like you want the List template to have a backwards method that
>>>>> returns a class that will iterate over the original list backwards.
>>>>> Seems
>>>>> like a simple enough thing to do.
>>>>>
>>>>> Or do I misunderstand?
>>>>>
>>>>> John
>>>>
>>>> Yeah - that's what I did. I was describing how I implemented a similar feature for non-arrays as another data point in the discussion.
>>>
>>> It seems to me that it doesn't necessarily need to be a different class, it could be another copy of the same class, containing the same info, backwards.
>>>
>>> Of course, sometimes a different class is preferrable.
>>>
>>> Regan
>>
>> Two points:
>> 1) it's actually a struct so that no garbage is created by foreaching
>> backwards. If I had to choose between writing a for loop that steps
>> backwards and writing a foreach loop that generating garbage I'd choose
>> writing the for loop - but that's me.
>
>Yeah, this is what I was thinking about when I said that a different class (I meant to include struct) was preferrable sometimes.
>
>> 2) a different type is needed because foreach on a regular List means forwards foreach and I decided that storing a flag as part of a general List just for backwards traversals wasn't worth the storage space.
>
>You're probably right. Unless you were doing a lot of list reversals the common case would never need/use it.
>
>I was thinking that the simplest solution is to go:
>
>class List {
>   List backwards() {
>     List l = new List();
>     foreach(Item i; this) {
>       l.addStart(i);
>     }
>     return l;
>   }
>}
>
>in other words, make a new list, put the items in it in reverse order, return that.
>
>But, as you say, more garbage, less efficient.
>
>> The actual implementation factors out the for loop into a function that the regular List calls with a step of +1 and the BackwardsList (or whatever name I used) calls with step -1.
>
>Cunning, I'll have to have a look at that code at some stage.
>
>Regan