Iterators (Was: Re: Lazy eval -- an example issue)

[Chris Nicholson-Sauls]

Sean Kelly wrote:
> Oskar Linde wrote:
> 
>> Sean Kelly wrote:
>>
>>> Walter Bright wrote:
>>>
>>>>
>>>> I've struggled to get people to accept the {} version ever since D 
>>>> adopted anonymous delegates. Haven't made much headway in getting 
>>>> such used or in it having any sort of significant impact. How many 
>>>> have made a "dotimes(n, exp)" function or any sort of syntax 
>>>> extension using it? None that I've seen.
>>>
>>>
>>> I've been working on a predicate-oriented algorithm module on and off 
>>> for the past few weeks.  A few looping constructs have been left out 
>>> because foreach seems a preferable solution in D, but the rest is 
>>> coming along nicely.  
>>
>>
>> Interesting. I have been doing some of this myself too, but my 
>> available time has been limited.  I have also been looking at the 
>> concept of iterators. I agree that foreach is the preferable solution, 
>> but in some cases, only supporting foreach is too limited. For 
>> example, only using foreach, you can not iterate over two collections 
>> simultaneously.
>>
>> It would be great if we could come up with a standardized Iterator 
>> concept for D that supported both foreach style iteration (opApply) 
>> and some kind of single step iteration (maybe Java-style next/hasNext).
> 
> 
> I agree.  And given D's somewhat limited overloading mechanism, there 
> may simply be no point in trying to support pointers as iterators (ie. 
> to use traits templates).  This suggests that some sort of 
> self-contained design may be best, but I haven't thought about the issue 
> enough to comment on the details.
> 
>> Here is a sample of how it could look (but this particular sample 
>> seems to give a segfault on DMD 0.165 for some reason):
>>
>> template opApplyMixin() {
>>   int opApply(int delegate(inout ValueType v) dg) {
>>     ValueType *t;
>>     while(hasNext()) {
>>       t = next();
>>       if (auto status = dg(*t))
>>     return status;
>>     }
>>     return 0;
>>   }
>> }
>>
>> /// Simple array iterator wrapper
>> struct ArrayIterator(T) {
>>   T[] arr;
>>   alias T ValueType;
>>
>>   T* next() { T* r = arr.ptr; arr = arr[1..$]; return r; }
>>   bool hasNext() { return arr.length > 0; }
>>   mixin opApplyMixin;
>> }
> 
> 
> So this would cover unidirectional iterators (forward and reverse) but 
> not bidirectional iterators?  Perhaps we need a hasPrev as well?  And 
> then there's random access iterators...
> 
>> I have been looking at implementing many of my functional algorithms 
>> as array views/iterators. For example:
>>
>> foreach(word; read!(char)("file.txt").splitIterate(&isSpace)) {
>>     writefln("%s",word);
>> }
>>
>> where splitIterate is implemented just as the regular split, but 
>> instead of allocating and returning char[][] array, it is implemented 
>> as an iterator returning the next char[] slice for each iteration 
>> without allocating any extra data.
> 
> 
> I think Matthew played with this idea a bit in DTL, but I don't think he 
> got quite this far.  It's a great idea however.  I can't recall if he 
> had a name for it, but "view" seems to fit.
> 
>> read could probably be implemented in a smart way, reading the file a 
>> certain chunk at a time. Never using more than a constant amount of 
>> memory.
>>
>> Other functions as iterators I have been implementing are:
>>
>> split(array,predicate|substring|element)
>> select(array,predicate|element)
>> reverse(array)
>> range(start,stop,next)
>> generate(init,next)
>> map(array,func)
>> indexmap(array,indexarray|nextindexfunc)
>> and so on...
> 
> 
> That's a solid proof of concept :-)
> 
> 
> Sean

I still think a good move would be to allow delegates as foreach aggregates.  Then a class 
could expose "iterators" in the form of methods, and algorithms could be represented as 
member delegates.

-- Chris Nicholson-Sauls