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

[Joseph Rushton Wakeling]

On Tuesday, 23 June 2020 at 16:20:26 UTC, Andrei Alexandrescu 
wrote:
> On 6/23/20 9:07 AM, Paul Backus wrote:
>> I don't think it's a given that tail() is less efficient than 
>> popFront(). Here's a program where both tail() and popFront() 
>> produce the same assembly with `ldc -O2`:
>> 
>> https://d.godbolt.org/z/-S_JoF
>
> With arrays, no problem. Two words to copy, easy to track, 
> enregister etc. With elaborate ranges, definitely a problem.
>
> ...
>
> There's "onerous" somewhere in there, too. I agree with Steve 
> who said implementing recursive variants of most range 
> algorithms in Phobos would be onerous.
>
> The each() primitive I discussed may work nice actually because 
> it allows recursion to be done in only itself, instead of every 
> algorithm.

I'm struck that no one AFAICS has suggested the following 
alternative: instead of `tail`, to allow popFront() (and if 
implemented, popBack()) to return an `Option!(ElementType, None)`.

What is returned would be either the popped element, or None if 
no more elements remain (with the nice by-product of no longer 
getting assert failures if pop{Front,Back} are called when the 
range is empty).

This might allow some natural API evolution along the following 
lines:

   * an input range need only implement such an option-based 
popFront() and
     no other methods

     - for backwards compatibility, we could also support 
implementing `front`
       and a `void`-returning popFront()

   * a forward range would additionally implement `front` and 
`save` methods:

     - `front` because, since a forward range is deterministic, it 
should
       always be possible to know up front (pun intended...) what 
the first
       element should be

     - `save` for the usual reasons

   * all other range types should derive naturally from this

     - we might want to consider a more fine-grained approach to 
bidirectional
       ranges, e.g. allowing a bidirectional input range with 
option-returning
       popFront and popBack

   * over time we could/should deprecate void-returning 
pop{Front,Back}, and
     possibly also defining `front` or `back` if `save` is not 
also defined

The approach of having only option-returning popFront would be 
particularly useful for input ranges where the front cannot or 
should not be predefined on construction (e.g. RNGs, or stuff 
that wraps them like RandomSample and friends).

(Is there actually a good example of an input range where the 
first element can be predefined on construction in a way that 
isn't -- like pseudo-RNGs -- an implementation detail that one 
probably wants to hide from the user?)