View mode: basic / threaded / horizontal-split · Log in · Help
November 05, 2006
Re: foreach vs. iterators
Bill Baxter wrote:
> Bill Baxter wrote:
>> Sean Kelly wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Still, I think it's useful to have in an iterator, so perhaps 
>>>> something roughly like this:
>>>>
>>>> interface Iterator(T)
>>>> {
>>>>     T val();
>>>>     T next();
>>>>     bool hasNext();
>>>> }
>>>
>>>
>>>
>>> Err... this doesn't work for an iterator returned for an empty 
>>> container.  
>>
>>
>> It's fine if you define the behavior to be that you have to call 
>> next() once to get the first value.  So for iteration idiom becomes:
>>
>> T v;
>> while(c.hasNext()) )
>> {
>> }
> 
> ....another victem of Ctrl+Enter....
> 
> while(c.hasNext())
> {
>    T v = c.next();
> }
> 
> I think an alias for T also needs to be a part of the definition of the 
> iterator.  Like  alias T value_type.

I don't think it's necessary, but it may be convenient.  For example, 
this should work:

typeof(c.next());

but that obviously requires an instance of the iterator.  And it's 
perhaps a bit confusing.

> Also would do you do a mutating iteration over collections of basic 
> value types (eg floats), structs, and classes?  I.e. if you want to do 
> something like:
> 
> while(c.hasNext())
> {
>    T v = c.next();
>    v += 2;
> }
> where T could be float, struct, or class.  Ok, class case is fine, but 
> the other two aren't clear to me.  Mutable iterator over structs could 
> maybe return a pointer to each struct.  Basic value type, I'm not sure. 
>  Just woke up though... maybe it's obvious and my head just isn't 
> working yet.

Yeah, perhaps returning a pointer is better.  The lack of reference 
types in D can make things like this a bit awkward.
November 05, 2006
Re: foreach vs. iterators
Sean Kelly wrote:
> Bill Baxter wrote:
> 
>> Sean Kelly wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Still, I think it's useful to have in an iterator, so perhaps 
>>>> something roughly like this:
>>>>
>>>> interface Iterator(T)
>>>> {
>>>>     T val();
>>>>     T next();
>>>>     bool hasNext();
>>>> }
>>>
>>>
>>>
>>> Err... this doesn't work for an iterator returned for an empty 
>>> container.  
>>
>>
>> It's fine if you define the behavior to be that you have to call 
>> next() once to get the first value.  So for iteration idiom becomes:
>>
>> T v;
>> while(c.hasNext()) )
>> {
>> }
> 
> 
> Yup, but this seems confusing with the presence of val() methods.

I'm not sold on val() yet.  :-)

--bb
November 06, 2006
Re: foreach vs. iterators
Bill Baxter wrote:
> Sean Kelly wrote:
>> Bill Baxter wrote:
>>
>>> Sean Kelly wrote:
>>>
>>>> Sean Kelly wrote:
>>>>
>>>>> Still, I think it's useful to have in an iterator, so perhaps 
>>>>> something roughly like this:
>>>>>
>>>>> interface Iterator(T)
>>>>> {
>>>>>     T val();
>>>>>     T next();
>>>>>     bool hasNext();
>>>>> }
>>>>
>>>>
>>>>
>>>> Err... this doesn't work for an iterator returned for an empty 
>>>> container.  
>>>
>>>
>>> It's fine if you define the behavior to be that you have to call 
>>> next() once to get the first value.  So for iteration idiom becomes:
>>>
>>> T v;
>>> while(c.hasNext()) )
>>> {
>>> }
>>
>>
>> Yup, but this seems confusing with the presence of val() methods.
> 
> I'm not sold on val() yet.  :-)
> 
> --bb

For what it's worth, C# implements it like this:

    public interface IEnumerator
    {
	public bool MoveNext();
	public object Current { get; }
	public void Reset();
    }

It seems that MoveNext() must be called before Current becomes valid 
(assuming that there are any items in the collection).  If Current is 
accessed without having an object to return, it throws an exception.  So 
a while loop might look like:

    while (e.MoveNext())
    {
        object obj = e.Current;
        Console.WriteLine(obj);
    }

C#'s foreach loop also works with IEnumerator, as:

    foreach (object obj in c)
    {
        Console.WriteLine(obj);
    }

where c is an object that implements the IEnumerable interface, which 
has a single GetEnumerator() method.

I'm not suggesting that D do the same thing as C#, but I thought that 
some of the above might be relevant to this discussion.

-Dave
November 06, 2006
Re: foreach vs. iterators
Sean Kelly wrote:
> Walter Bright wrote:
> 
>> Sean Kelly wrote:
>>
>>> I think I agree, but for the sake of argument, how would D handle 
>>> 'find'  operations on sequences that don't support opIndex?  At some 
>>> point, a generalizable bookmark is almost necessary for a faithful 
>>> implementation of some C++ algorithms.  Also, many of these 
>>> algorithms also require iteration across two sequences 
>>> simultaneously, which doesn't map very cleanly into foreach.  
>>> Consider a substring-style find operation (std::search), for example, 
>>> where both the pattern and target types do not support opIndex or 
>>> opSlice.  I might argue that it's a bit silly or unrealistic to 
>>> desire such an operation, but the C++ algorithm library does support it.
>>
>>
>> I think the target types will have to support opIndex or opSlice.
> 
> 
> Forgive me for resurrecting a horribly battered equine, but I was 
> thinking about this a bit tonight and I've decided that foreach, 
> foreach_reverse, and array operations are not a sufficient general 
> substitute for C++ iterators.
> 
> For example, let's say I want to compute the set union of two sorted 
> ranges, one of size M, the other of size N.  By iterating across the two 
> ranges simultaneously is is easy to see that the complexity for the 
> operation will be max(M,N).  In C++ this is easily accomplished using 
> forward iterators, and the ranges can be anything from arrays to SQL 
> result sets.
> 
> In D however, there is no way to iterate across multiple ranges 
> simultaneously using foreach, so opIndex must be used instead.  With 
> containers that have a constant-time lookup cost this isn't a big deal, 
> but what if these containers are binary trees?  The complexity for such 
> an operation would be M(log(M)) + N(log(N)).
> 
>  From this it seems clear that foreach is not sufficiently adaptable to 
> meet the needs of all sequential algorithms and opIndex is not a 
> reasonable substitute for all cases where foreach may not be used.  What 
> alternatives do we have?  So far, iterator variants are all I've been 
> able to come up with.
> 
> 
> Sean

I have created a monster!!!


// a class that can iterate over it's contents and another
// iterator's contents in order

class Foo
{

	// return an iterator
 int delegate(int delegate(inout U))
       opApplyWith(int delegate(inout U) t)
 {
	// make a class to form delegate
  auto ret = new class
  {
	// context
   int delegate(inout U) t;

	// iterator
   int ret(int delegate(inout U) dg)
   {
    int i=0;
	// loop on other
    foreach(inout U u, t)
    {
	// sub loop on self
     while(i<sortedUs.length && sortedUs[i] < u)
      if(int r = dg(sortedUs[i++])) return r;
     if(int r = dg(u)) return r;
    }

   }
  };
	// set context
  ret.t = t;
	// return it
  return &ret.ret;
 }

	// loop on self only
 int opApply(int delegate(inout U) dg)
 {
  foreach(inout U u, sortedUs)
  {
   if(int r = dg(sortedUs[i++])) return r;
  }
 }

	// data for class
 U[] sortedUs;
}

	// use it.
int main()
{
 Foo f1, f2;
 foreach(U u; f1.opApplyWith(&f2.opApply))
 {
  use(u);
 }
}
November 06, 2006
Re: foreach vs. iterators
BCS wrote:

> I have created a monster!!!

Sure!  Why not?
opApplyWith is surely no less useful than opApplyReverse. ;-)
Oh, but we probably need opApplyWithReverse now too.  :-)

--bb
November 07, 2006
Re: foreach vs. iterators
Bill Baxter wrote:
> BCS wrote:
> 
>> I have created a monster!!!
> 
> 
> Sure!  Why not?
> opApplyWith is surely no less useful than opApplyReverse. ;-)
> Oh, but we probably need opApplyWithReverse now too.  :-)
> 
> --bb


Ahh. Err. I wasn't suggesting that foreach_with() be added, it just 
looked like a good name. I could have named it "Bob" and it would still 
do what I was intending but then no one would known right off what it is 
supposed to do.

The though is that making some sort of delegate/thunk/closure as an 
iterator can provide a lot of different iteration type patterns.
Next ›   Last »
13 14 15 16 17
Top | Discussion index | About this forum | D home