Algorithms & opApply

[Steven Schveighoffer]

On Tue, 24 Aug 2010 01:59:51 -0400, Fawzi Mohamed <fawzi at gmx.ch> wrote:

> On 24-ago-10, at 04:26, dsimcha wrote:
>
>> [...]
>> 3.  Ranges are the flagship way of iterating through an object in D, as  
>> they
>> should be.  opApply has its uses, but they're relatively few and far  
>> between.  I'm
>> wondering if anyone besides bearophile and I think supporting opApply  
>> is worth the
>> effort and potential bloat, if Walter cares enough to fix Bug 2443, and  
>> if Andrei
>> considers it to be a reasonable part of std.range/std.algorithm's  
>> design.
>
> I already defended opApply in the past let me put this here again:
>
> ranges abstract away one iteration step. This is useful because it means  
> that combining several of them, adancing in locksteo,... is possible and  
> easy to do
>
> opApply abstracts away a whole loop. This makes complex loops simpler to  
> realize without having to resort to fibers, and it allows *parallel*  
> looping in a natural way (which cannot be done directly using only  
> single iteration operations.
> In blip/dchem I use this quite a bit (for example for parallel loop  
> helpers, often my objects have obj.sLopp  
> obj.pLoop(blocksize=dafaultVal)).
> I like very much to be able to do foreach (x;obj.pLoop){...}
>
> Now they obviously are different kinds of abstractions, so looping in  
> lockstep is not possible with opApply, at most you can lockstep *one*  
> opApply with N iterators.
>
> About the operations in algorithm well I am not too sure how much  
> support there should be, if they require just looping then yes, but (for  
> example) I think that almost all of them would fail if feeded with a  
> parallel opApply.
> For sequential loops fibers can transform opApply in an iterator (just  
> as fibers can be used to easily make an iterator out of a complex loop).
> But fiber have a relatively high cost.
> So I suppose I would give support just to the basic stuff + conversion  
> for sequential loops (via fibers), keeping most of std.algorithm opApply  
> free


Building on this, (I once asked "do we need opApply anymore?"), I know of  
several reasons ranges do not replace opApply:

1. opApply is a more natural fit for virtual functions.
2. opApply can use the stack, ranges cannot.  This is useful for say  
iterating a binary tree without parent pointers.
3. opApply supports the full syntax of foreach, which can include multiple  
parameters in the loop.

I have proposed an enhancement in the past to make all callable symbols  
foreachable, including delegates, normal functions, and functors.  This  
would obviate the need for a special "opApply" function (just use opCall  
with the proper signature).

The bug is here: http://d.puremagic.com/issues/show_bug.cgi?id=2498

-Steve