std.v2020.algorithm etc[ WAS: Is run.d going to be expand for runtime and the phobos library?]

[Andrei Alexandrescu]

On 6/21/20 10:47 AM, Andrei Alexandrescu wrote:
> Was the better 
> alternative to make input ranges noncopyable? It only takes a couple of 
> hours of coding a bit of that up to see it's quite onerous.

To recap/put forth a few possible APIs for input ranges (that are not 
forward):

bool fetchNext(ref T target);

Spec: As long as the range is nonempty, assigns the next element to 
target and returns true. At end of range returns false without touching 
target.

Pros: works naturally with actual input ranges such as files and sockets.

Cons: does not work if T is qualified. Creates a copy of each element 
for forward ranges that exist in memory. That means essentially the API 
is impaired and most algorithms that work with input ranges would need 
to specialize for forward ranges, too. (FWIW this interface was first 
discussed before D had qualifiers). Composes so-so, consider 
implementations of filter (not bad) and map (not so nice).

T* fetchNext();

Spec: As long as the range is nonempty, returns a pointer to the next 
element in the range. At end of range returns null.

Pros: Simple and efficient for many ranges. Doesn't compose too well.

Cons: Issues with escape analysis and safety. Sometimes the pointer is 
scope, sometimes it's not depending on the range.

T fetchNext(ref bool done);
or
ref T fetchNext(ref bool done);

Spec: As long as the range is nonempty, sets done to false and returns 
the next element in the range. At end of range sets done to true and 
returns an arbitrary T.

Pros: works with qualified data.

Cons: inefficient or needs two versions depending on ref/value. 
Complicates life of clients.

Flag!"each" each(alias fun);

Spec: calls fun(x) for each element in the range x - an efficient 
generalization of opApply. If fun returns No.each, stops iteration (and 
also returns No.each). Otherwise, returns Yes.each. See 
https://dlang.org/library/std/algorithm/iteration/each.html.

Pros: works naturally and efficiently (assuming proper inlining) with 
many range types. Composes quite well, picture e.g. implementations of 
map and filter. Beautiful. Efficient implementation for forward ranges 
is immediate. Jives well with Oleg's famous take on iteration 
(http://okmij.org/ftp/papers/LL3-collections-talk.pdf).

Cons: ranges such as map, filter etc. would need to expose both each() 
(for input ranges) and the existing interface (for better than input 
ranges). A number of algorithms would need to be redone to take 
advantage of the new interface. The language integration is not as nice 
as with the (sadly inefficient) existing opApply.

At a point Sebastian Wilzbach and I discussed that several ranges should 
get an each() member function, but that never got finalized. Once each() 
is a member of prominent input range algos (can't hurt because people 
already can call the less efficient each() global function) and we 
accumulate experience with it, we can sanction it as a legit optional 
primitive for ranges.

One more thing before I forget - we should drop classes that are ranges. 
They add too much complication. The functionality would still be present 
by wrapping a polymorphic implementation in a struct.