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

[Stanislav Blinov]

On Saturday, 27 June 2020 at 12:25:34 UTC, Joseph Rushton 
Wakeling wrote:

> But -- for example -- what would it mean to have an input range 
> as part of a const or immutable data structure?  Forget the 
> strict interpretation of the current D keywords, let's just 
> think conceptually for a moment.  Do we want to think of an 
> immutable input range as just a source of input, with any 
> under-the-hood mutability just an implementation detail that 
> shouldn't be of interest to the external caller?  Do we 
> consider it a contradiction in terms?

An immutable or const input range just cannot be. An input range 
can't not be mutable.
If a range itself can implement a `tail()`, it's not an input 
range, it's a forward range. The only way for `tail()` to work 
with input ranges is to be a free function:

R tail(R)(R r)
if (isInputRangeWithAHypotheticalAPI!R)
{
     r.next(); // fetchNext(), advance(), whatever the API is
     return move(r);
}

and used like this:

input = move(input).tail;

(Yes, I'm still insisting that input ranges must be non-copyable).

> I also think it may be worth making a point of comparison to 
> Rust's iterators.  Obviously Rust has a different approach to 
> immutability than D -- the main concern is preventing multiple 
> mutable references to the same piece of data -- but there is a 
> very clear separation between iterators versus what they 
> iterate over, and generally speaking (probably because of that 
> separation) iterators themselves seem to be always implemented 
> as mutable.

True input ranges are basically Rust's iterators, i.e. their API 
should be

Optional!T next(); // in other words, a bool and a T

or variations thereof, as outlined by Andrei some pages back. 
IMHO, the above API is the cleanest. But there is also place for 
buffered input ranges (i.e. the currently existing API), see 
below.

> So, what I'm interested in is whether we can reliably rework 
> the input range API such that the only way to determine the 
> next element is to actually fetch it.

Both APIs have their place. A "true" input range (i.e. a 
generator) yields temporaries, and only needs a "fetch next" 
primitive. But the *algorithms* may require a buffer. Consider a 
`find`: it needs to return the needle and the remainder of the 
range. In order to find the needle it needs to pop it off from 
the "fetch next" haystack, irreversibly advancing it. If we want 
to keep `find` generic over input and forward ranges (i.e. 
returning a range), it will have to wrap the haystack into a 
buffered input range with the front/popFront API, placing the 
found needle at the front, i.e. hypothetically:

auto find(alias pred, Range, Needle)(Range range, auto ref const 
Needle needle)
if (isInputRangeWithAHypotheticalAPI!R)
{
     static struct Result
     {
         private typeof(Range.init.next()) buf;
         private Range src;

         // So long as the Optional holds a valid value, range is 
not empty
         @property bool empty() const { return !buf; }

         // Accessing an empty Optional would be illegal,
         // so the non-empty() invariant is observed.
         ref front() inout { return buf.value; }

         void popFront() { buf = src.next(); }
     }

     typeof(range.next()) current; // i.e. an Optional!ElementType
     while (true)
     {
         current = range.next;
         if (!current || pred(current.value, needle))
             break;
     }

     return Result(move(current), move(range));
}