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

[Stanislav Blinov]

On Sunday, 28 June 2020 at 16:37:23 UTC, Paul Backus wrote:
> On Sunday, 28 June 2020 at 15:33:48 UTC, Stanislav Blinov wrote:
>> On Sunday, 28 June 2020 at 14:12:39 UTC, Paul Backus wrote:
>>
>>> It sounds like what you are really trying to say here is that 
>>> input ranges and forward ranges should not use the same 
>>> interface, and that input ranges should instead implement 
>>> only `Option!T next()`.
>>
>> Not exactly. A given forward range may also implement such a 
>> `next`. [...] We should differentiate by some other artifact. 
>> I maintain that artifact should be copyability. Or we can keep 
>> the distinction based on the presence of save(), and live 
>> forever with the ambiguous semantics and the "don't use 
>> original after copy unless you know what you're doing" 
>> convention (yuck). Are there even other options besides 
>> accepting UB?
>
> If input ranges are only required to implement next(), then the 
> distinction will be that forward ranges implement head()/tail() 
> and input ranges don't. (In this scenario, head() and tail() 
> will of course be required to return the same result if called 
> multiple times.)

Just as forward ranges may implement `next()`, some input ranges 
may want to be buffered, i.e.:

struct Wrapped
{
     private typeof(src.next()) buf; // Optional!ElementType
     private Input src; // Input is a `next()` input range

     @property bool empty() const { return !buf; }
     T moveFront() { return buf.replace(T.init); }
     void popFront() { buf = src.next; }

     // no front, only moveFront
}

If we put a hard requirement on input ranges to *only* exist with 
the next() interface, this will shut down possible optimizations 
that buffering enables. We can't implement a buffering range in 
terms of the `next()` interface, a staggered fetch + advance is 
required. (next() may overwrite the internals of the buffer 
before client has a chance of reading the value).

>>> My example was a response to the specific claim that "an 
>>> immutable input range cannot exist." Specifically, it was a 
>>> counterexample demonstrating that the claim is false. As I'm 
>>> sure you can see, the claim is still false even if we agree 
>>> to use next() instead of tail() for input ranges, since 
>>> next() is obviously allowed to be impure.
>>
>> I can't see that. I don't see how you're falsifying that claim
>> when in order to implement the range you need mutable state.
         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Ok, I'll show you. Here's the same range implemented using 
> next() instead of front() and tail():
>
>             Optional!char next() const
>             {
>                 char c;
>                 ssize_t nread = read(fd, cast(void*) &c, 1);
                                   ^^^^
>
>                 if (nread == 0)
>                     return no!char;
>                 else if (nread == 1)
>                     return some(c);
>                 else
>                     throw new Exception("Error reading file");
>             }
>         }
> Once again, `stdinByChar` is an input range, and it is 
> immutable. QED.

:) Fine. An input range can't exist without mutable state. Is 
that statement more agreeable for you?