www.digitalmars.com         C & C++   DMDScript  

D - foreach iterators in D

reply "Thomas D. Marsh" <thomas.marsh seznam.cz> writes:
Okay, we Sather guys have very wordily discussed iterators in the "Using
Sather as a Model" thread. The question is, does anyone like them,
understand them, or care about them?

The ultimate goal is to be able to express:

        int[] myarr = ...
        foreach value in myarr
        {
                printf("%d\n", value);
        }

Expressed in terms I have been discussing this might look something like:

        int[] myarr = ...
        loop
        {
                printf("%d\n", myarr.elt());
        }

Where the .elt() method is an iterator. Of course "foreach" could be
syntactical sugar for "loop ... obj.elt(); .."; or, the implementation of
iterators simply may not be of interest to anyone.

Walter, have you been watching the discussion, and do you have any opinions?

--thomas

-- 
The UNIX philosophy basically involves giving you enough rope to
hang yourself.  And then a couple of feet more, just to be sure.
Apr 17 2003
next sibling parent "Luna Kid" <lunakid neuropolis.org> writes:
"Thomas D. Marsh" <thomas.marsh seznam.cz> wrote in message
news:b7m2jr$ei0$1 digitaldaemon.com...

 Okay, we Sather guys have very wordily discussed iterators in the "Using
 Sather as a Model" thread. The question is, does anyone like them,
 understand them, or care about them?

 The ultimate goal is to be able to express:

         int[] myarr = ...
         foreach value in myarr
         {
                 printf("%d\n", value);
         }



For one, I absolutely welcome everything that can
cleanly increase my expressive power in a language.

In fact, usually, (depending also on the task, though)
nothing is more important to me than that, when
considering a language.

Luna Kid
Apr 17 2003
prev sibling next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
The ultimate goal is to be able to express:

        int[] myarr = ...
        foreach value in myarr
        {
                printf("%d\n", value);
        }

Expressed in terms I have been discussing this might look something like:

        int[] myarr = ...
        loop
        {
                printf("%d\n", myarr.elt());
        }

Where the .elt() method is an iterator.



This example is simpler in functional style:







Mark
Apr 17 2003
parent reply Chris Lawson <cl nospamhere.tinfoilhat.ca> writes:
Mark Evans wrote:

 
 
 This example is simpler in functional style:
 

 

 

 
 Mark
 
 


I like this syntax.  But, how would you deal with conditionals?  Trivial 
example:

foreach thing in myarray
{
	if ( thing > n ) { do stuff }
	else { do some other stuff }
}

Chris
Apr 17 2003
parent reply Mark Evans <Mark_member pathlink.com> writes:
I like this syntax.  But, how would you deal with conditionals?  Trivial 
example:

foreach thing in myarray
{
	if ( thing > n ) { do stuff }
	else { do some other stuff }
}




The pound sign was inspired by Mathematica (with deeper
etymology elsewhere I suppose) so here's a working
example to answer your question.  If[...]& defines
an anonymous function.  (* Comments *) are like so.

Mathematica is an exceptional language but suffers from a
fairly bad syntax that I do not advocate.

Mark

myarray = {"Albert", "Sally", "Stephen", "Ingrid"};
i=0;
result= Map[If[OddQ[i++],


myarray]

(* produces result of *)
{"Al","S","St","I"}
Apr 17 2003
parent "Thomas D. Marsh" <thomas.marsh seznam.cz> writes:
Are we still talking about D? :)

--thomas

Mark Evans wrote:


 

I like this syntax.  But, how would you deal with conditionals?  Trivial
example:

foreach thing in myarray
{
if ( thing > n ) { do stuff }
else { do some other stuff }
}


 
 
 
 The pound sign was inspired by Mathematica (with deeper
 etymology elsewhere I suppose) so here's a working
 example to answer your question.  If[...]& defines
 an anonymous function.  (* Comments *) are like so.
 
 Mathematica is an exceptional language but suffers from a
 fairly bad syntax that I do not advocate.
 
 Mark
 
 myarray = {"Albert", "Sally", "Stephen", "Ingrid"};
 i=0;
 result= Map[If[OddQ[i++],


 myarray]
 
 (* produces result of *)
 {"Al","S","St","I"}


-- 
A truly great man will neither trample on a worm nor sneak to an emperor.
                -- B. Franklin
Apr 22 2003
prev sibling next sibling parent reply "C. Sauls" <ibisbasenji yahoo.com> writes:
"Thomas D. Marsh" <thomas.marsh seznam.cz> wrote in message
news:b7m2jr$ei0$1 digitaldaemon.com...

 Okay, we Sather guys have very wordily discussed iterators in the "Using
 Sather as a Model" thread. The question is, does anyone like them,
 understand them, or care about them?

 The ultimate goal is to be able to express:

         int[] myarr = ...
         foreach value in myarr
         {
                 printf("%d\n", value);
         }

 Expressed in terms I have been discussing this might look something like:

         int[] myarr = ...
         loop
         {
                 printf("%d\n", myarr.elt());
         }

 Where the .elt() method is an iterator. Of course "foreach" could be
 syntactical sugar for "loop ... obj.elt(); .."; or, the implementation of
 iterators simply may not be of interest to anyone.

 Walter, have you been watching the discussion, and do you have any


opinions?

 --thomas

 --
 The UNIX philosophy basically involves giving you enough rope to
 hang yourself.  And then a couple of feet more, just to be sure.


Personally I do love the idea of a foreach loop construct, but have two
suggestions.
1) A syntax more like the C-style the rest of the language follows.
            FOREACH (array; indentifier)
2) Key=>Value pair iteration for associative arrays.
            FOREACH (array; key, value)

For non-associative arrays, the latter could either be illegal, or else the
key set to the numeric index.  With the .keys and .values type properties in
place, this shouldn't be a problem to implement.

--Chris
Apr 18 2003
parent reply "Thomas D. Marsh" <thomas.marsh seznam.cz> writes:
Hi!

As a point of contrast I will give some examples from other languages. A
foreach loop as you described would probably look like the following:

        int [] arr = somfunc();
        foreach (arr; int i)
        {
                ...
        }

This is syntactically familiar compared to the C-style for loop. Note that I
had to add storage for "i".


PYTHON

Python implements these constructs with a new keyword "in":

        arr = [1,2,3]
        for i in arr:
                ...

which I actually find to be clearer. Maybe my eyes just aren't used to
"foreach (arr; int i)". Python has the following idiom for iterating over
dictionaries:

        dict = {'a': 1, 'b': 2, ...}
        for (key,val) in dict.keys():
                ...

Notably, python 1.2.2 introduces generators/iterators, so these idioms (or
perhaps their implementations) may change in order to reduce their cost.


RUBY

Ruby, which natively supports iterators, allows you to perform the
following:

        arr = [1,3,5]
        arr.each { |i|
                .. do something with i..
        }

Actually, since iterators are pervasive in the language, all other examples
will be similar to code snippets I've given in my other posts.





and python's:

        int [] arr = new int [] {1,2,3}
        foreach (int i in arr)
        {
                ...
        }


constructs. Perhaps there is one, but I couldn't find it 


PERL

This example brought back some bad memories which I had long ago buried:

        foreach $elem ( arr)
        {
        }

foreach is just syntactic sugar for the keyword "for", so you can also say:

        for $elem ( arr) { ... }

OTHER FORMS

Of course, there is the possibility to depart extravagantly from the
ALGOL-ish constructs altogether:

        map(lambda (x) ...)

this example relying on anonymous functions. And, of course the iterators of
Sather:

        arr:ARRAY{INT} := |1,2,3|;
        loop
          #OUT+ arr.elt! + "\n";
        end;


REVERSE FORMS AND THE DIFFERENT APPROACHES

One of the items listed on the "Future Directions" on the D home page says:

        A generic way to iterate across a collection, i.e. a foreach construct
instead of a for loop. A reverse iterator will be needed, too. This has
some interesting consequences.

 - The map/apply approach of functional languages requires a list reversal
before iteration which may be expensive. Lisp and relatives can optimally
handle list operations natively, and hence are well suited to this form.
-But without major changes to D to support anonymous functions

- the iterator form could be implemented in various forms (elt! and relt!,
for example, plus maybe rand_elt!), but there isn't a clear desire for
iterators except amongst us Sathery types. Though, by far, I consider this
to be the best alternative.

- An additional keyword is required in the case of the algo-ish forms, but
the actual implementation would look like iterators under the covers.



        foreach (int i in arr) { ... }
        foreach (int key, int val in coll) { ... }
        foreach reverse (int i in arr) { ... }
        foreach reverse (int key, int val in coll) { ... }

This is most in keeping with the D style of doing things as far as I can
see.

--thomas

C. Sauls wrote:

 Personally I do love the idea of a foreach loop construct, but have two
 suggestions.
 1) A syntax more like the C-style the rest of the language follows.
             FOREACH (array; indentifier)
 2) Key=>Value pair iteration for associative arrays.
             FOREACH (array; key, value)
 
 For non-associative arrays, the latter could either be illegal, or else
 the
 key set to the numeric index.  With the .keys and .values type properties
 in place, this shouldn't be a problem to implement.
 
 --Chris


-- 
To say you got a vote of confidence would be to say you needed a vote of
confidence.
                -- Andrew Young
Apr 22 2003
next sibling parent reply Mark Evans <Mark_member pathlink.com> writes:
Functional application requires neither anonymous functions nor list reversal.
You can use named functions.

If D now offers first-class functions then it should support the functional
idiom.  Map is a higher-order function of two arguments, a function and a list.
The output is a new list.  You can also define a scan which does identical list
walking, but returns void, i.e. list modification in place.

Mark
Apr 22 2003
parent C. Sauls <C._member pathlink.com> writes:
In article <b84083$1gh0$1 digitaldaemon.com>, Mark Evans says...

Functional application requires neither anonymous functions nor list reversal.
You can use named functions.

If D now offers first-class functions then it should support the functional
idiom.  Map is a higher-order function of two arguments, a function and a list.
The output is a new list.  You can also define a scan which does identical list
walking, but returns void, i.e. list modification in place.

Mark


I've worked with 'map' before in my foray with ColdC servers, along with 'hash',
'find', and 'filter' which all work in more or less the same way.  I think it
would be nice to have their equivelant(s) in D.

(For more info on ColdC's map/hash/find/filter expressions:)
http://ice.cold.org:1180/bin/help?node=$help_coldc_loop_expr

-- C. Sauls
Apr 24 2003
prev sibling next sibling parent "Peter Hercek" <vvp no.post.spam.sk> writes:
"Thomas D. Marsh" <thomas.marsh seznam.cz> wrote in message
news:b83qfj$1cci$1 digitaldaemon.com...




 and python's:

         int [] arr = new int [] {1,2,3}
         foreach (int i in arr)
         {
                 ...
         }


 constructs. Perhaps there is one, but I couldn't find it


It does not have anything special for associativecollections.
 It works like this:

foreach(DictionaryEntry myEntry in myDictionary){
  Console.WriteLine(myEntry.Key + ": " + myEntry.Value);
}

... or like this:

foreach (string myStr in myHastable.Keys){
  Console.WriteLine(myStr + ": " + myHastable[myStr]);
}

When a collection implements a method (GetEnumerator), which
 returns an iterator (something with MoveNext and Current),
 then foreach is available for the collection.
Apr 22 2003
prev sibling parent Mark T <Mark_member pathlink.com> writes:



and python's:

        int [] arr = new int [] {1,2,3}
        foreach (int i in arr)
        {
                ...
        }
Apr 25 2003
prev sibling next sibling parent reply "Dario" <supdar yahoo.com> writes:
We mustn't forget that 'in' is an operator in D.
If we use it in the foreach construct it would be misleading to those who
read the code,
especially in particularly involuted espression.

I prefer a sintax like:
    char[][] blah;
    foreach(char[] a; blah) {}
which Thomas D. Marsh proposed.

Anyway, there are other construct which we have to think about.
For example, something like:
    char[] A, B;
    foreach(char a; A)(char b; B)
        A = B;
Which would be equivalent to:
    char[] A, B;
    assert(A.length == B.length);
    for(int i; i < A.length; i++)
        A[i] = B[i];

What D needs is an intuitive sintax which would be able to replace the C
'for' sintax
in all (or almost all) its uses. (To be sincere, I wish D will drop the ugly
'for' construct
in the future.)

Dario
Apr 27 2003
parent reply "Thomas D. Marsh" <thomas.marsh seznam.cz> writes:
Hello Dario,

Credit where credit is due: the foreach example you gave was Chris Sauls'
example. I think the in operator having dual purpose is possible, though,
arguably, may lead to confusion. Python for example has:

        for x in list:
                foobar(x)

as well as

        if x in list:
                ...

with different meaning in each context. It doesn't really matter to the
compiler as it has to treat looping expressions specially anyhow. I haven't
heard about any complaints in my time with python regarding the dual use of
the 'in' keyword in this case.

Just to throw some more syntactic variety out there, we'll take your example


        char[] A, B;

        foreach (char a in A, char b in B)
        {
        }

Or what about this:

        foreach (char a in A reverse, char b in B)
        {
        }

in the case of reverse iteration?

--thomas

Dario wrote:


 We mustn't forget that 'in' is an operator in D.
 If we use it in the foreach construct it would be misleading to those who
 read the code,
 especially in particularly involuted espression.
 
 I prefer a sintax like:
     char[][] blah;
     foreach(char[] a; blah) {}
 which Thomas D. Marsh proposed.
 
 Anyway, there are other construct which we have to think about.
 For example, something like:
     char[] A, B;
     foreach(char a; A)(char b; B)
         A = B;
 Which would be equivalent to:
     char[] A, B;
     assert(A.length == B.length);
     for(int i; i < A.length; i++)
         A[i] = B[i];
 
 What D needs is an intuitive sintax which would be able to replace the C
 'for' sintax
 in all (or almost all) its uses. (To be sincere, I wish D will drop the
 ugly 'for' construct
 in the future.)
 
 Dario


-- 
All power corrupts, but we need electricity.
Apr 27 2003
next sibling parent Ilya Minkov <midiclub 8ung.at> writes:
While the semantics is different, the "meaning" probably isn't.

If "in" means testing whether the value is contained in a set, then it 
would apply both to "foreach (x in set)", and to "if (x in set)". Note 
that foreach acts so, as if it would go and test every possible x 
whether it belongs to the set, which boils down to the same semantics as 
"if (x in set)". Obviously, this would be a wrong guide for an 
implementation, but it feels right as a mnemonic. Thinking out new and 
unnatural keywords for every single case isn't a solution either... 
That's also the justification for function overloading.

How about handling different types as sets, not only associative arrays?
How about associative arrays with no value associated, which would be so 
to say pure sets then?

How about a completely alternative for syntax:

for (type a = 1 to x) {}
for (type a = 1 to x step c) {}
for (type a = 1 downto x step c) {}
for (type a in s) {}

"type" is obviously only requiered to create new variables.
If someone would call it keyword abuse, you can also rename these "for" 
into the more verbose "foreach". This would also make sure that noone 
ocassionally confuses it with "if(...in...)", although i somehow 
consider plain "for" more appropriate.

-i.


Thomas D. Marsh wrote:

 Hello Dario,
 
 Credit where credit is due: the foreach example you gave was Chris Sauls'
 example. I think the in operator having dual purpose is possible, though,
 arguably, may lead to confusion. Python for example has:
 
         for x in list:
                 foobar(x)
 
 as well as
 
         if x in list:
                 ...
 
 with different meaning in each context. It doesn't really matter to the
 compiler as it has to treat looping expressions specially anyhow. I haven't
 heard about any complaints in my time with python regarding the dual use of
 the 'in' keyword in this case.
 
 Just to throw some more syntactic variety out there, we'll take your example

 
         char[] A, B;
 
         foreach (char a in A, char b in B)
         {
         }
 
 Or what about this:
 
         foreach (char a in A reverse, char b in B)
         {
         }
 
 in the case of reverse iteration?
 
 --thomas
 
 Dario wrote:
 
 

We mustn't forget that 'in' is an operator in D.
If we use it in the foreach construct it would be misleading to those who
read the code,
especially in particularly involuted espression.

I prefer a sintax like:
    char[][] blah;
    foreach(char[] a; blah) {}
which Thomas D. Marsh proposed.

Anyway, there are other construct which we have to think about.
For example, something like:
    char[] A, B;
    foreach(char a; A)(char b; B)
        A = B;
Which would be equivalent to:
    char[] A, B;
    assert(A.length == B.length);
    for(int i; i < A.length; i++)
        A[i] = B[i];

What D needs is an intuitive sintax which would be able to replace the C
'for' sintax
in all (or almost all) its uses. (To be sincere, I wish D will drop the
ugly 'for' construct
in the future.)

Dario
Apr 28 2003
prev sibling parent "Dario" <supdar yahoo.com> writes:
 Credit where credit is due: the foreach example you gave was Chris Sauls'
 example.


Ops, I apologize.


 I think the in operator having dual purpose is possible, though,
 arguably, may lead to confusion.


Yes, it can be used in the foreach construct, but I think it's better not to
assign more
meaning to the in operator. Not only it would lead to confusion in
expressions like
    foreach(char[] a in b in c ? c : d) ...
but maybe it would result in a more complex compiler implementation too.
Apr 28 2003
prev sibling parent reply "Walter" <walter digitalmars.com> writes:
"Thomas D. Marsh" <thomas.marsh seznam.cz> wrote in message
news:b7m2jr$ei0$1 digitaldaemon.com...

 Walter, have you been watching the discussion, and do you have any


opinions?

Yes. I decided long ago that D needed a foreach, I just haven't implemented
it yet.
May 16 2003
parent reply "C. Sauls" <ibisbasenji yahoo.com> writes:
 Yes. I decided long ago that D needed a foreach, I just haven't


implemented

 it yet.


Good to hear!  Though I'd like to retract a point of my own.. I remember
suggesting key->value pair iterators via a syntax such as:

    int[char[]] array;
    ...
    char[] key;
    int value;
    for (array; key:value)
    { ... }

But after thinking about it a little I realize that its not really necessary
since we can just:

    int[char[]] array;
    ...
    char[][] keys = array.keys;
    char[] key;
    int value;
    for (keys; key)
    { ... }

Doesn't seem that much worse to me.

--C. Sauls
May 16 2003
parent reply "Daniel Yokomiso" <daniel_yokomiso yahoo.com.br> writes:
"C. Sauls" <ibisbasenji yahoo.com> escreveu na mensagem
news:ba3k1v$1hlj$1 digitaldaemon.com...

 Yes. I decided long ago that D needed a foreach, I just haven't


 implemented

 it yet.


 Good to hear!  Though I'd like to retract a point of my own.. I remember
 suggesting key->value pair iterators via a syntax such as:

     int[char[]] array;
     ...
     char[] key;
     int value;
     for (array; key:value)
     { ... }

 But after thinking about it a little I realize that its not really


necessary

 since we can just:

     int[char[]] array;
     ...
     char[][] keys = array.keys;
     char[] key;
     int value;
     for (keys; key)
     { ... }

 Doesn't seem that much worse to me.

 --C. Sauls


    Hi,

    It can be really worse. Compare these:


foreach (key, value in dict) { // O(N) complexity or something like that
    printf("%.*s => %.*s\r\n", key.toString(), value.toString());
}

foreach (key in dict) { // O(N) complexity or something like that
    printf("%.*s => %.*s\r\n", key.toString(),
           dict[key]    // must lookup key again in container, we hope it's
O(1)
           .toString());
}


    The lookup complexity may be O(1), O(log(N)) or even O(N * N) (I don't
know may be some bizarre kind of datastructure, who knows). But it'll
probably be some kind of performance leak. We could get away with other
syntax:


template TEntry(T, U) {
    struct Entry {
        T key;
        U value;
    }
}

instance TEntry(A,B).Entry entry;
foreach (entry in dict.entries) {
    printf("%.*s => %.*s\r\n", entry.key.toString(),
entry.value.toString());
}


    But we need this idiom. There are a bunch of sites talking about how
people keep iterating like this (using foreach with the keys, then looking
up the values) in Perl and Python, getting lousy performance because of this
"simple" idiom.

    Best regards,
    Daniel Yokomiso.


"My opinions may have changed, but not the fact that I am right."
 - Ashleigh Brilliant


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.481 / Virus Database: 277 - Release Date: 13/5/2003
May 19 2003
parent "C. Sauls" <ibisbasenji yahoo.com> writes:
Point made entirely.

-- C. Sauls
May 23 2003