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

Paul Backus snarwin at gmail.com
Tue Jun 23 21:19:39 UTC 2020


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.

Do you (or anyone else reading this--feel free to chime in) have 
an example in mind of such an "elaborate range"? If so, I'd be 
happy to do the legwork of running additional experiments. No 
need to settle for speculation here when we can have actual data.

>> Even if we assume for the sake of argument that "recursion == 
>> difficult", I would still say that "difficult" is an 
>> improvement over "impossible".
>
> 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.

Again, if you, Steve, or anyone else in this thread have any 
examples in mind, I'd be happy to run the experiment of writing 
recursive versions myself.

> The each() primitive I discussed may work nice actually because 
> it allows recursion to be done in only itself, instead of every 
> algorithm.

Even without making `each` a primitive, you can do this. 
Implement a few fundamental algorithms like `each`, `map`, 
`filter`, and `fold` using recursion, and many others can be 
built on top of them.


More information about the Digitalmars-d mailing list