In general, who should do more work: popFront or front?

[Paul Backus]

On Tuesday, 15 June 2021 at 04:24:09 UTC, surlymoor wrote:
> All my custom range types perform all their meaningful work in 
> their respective popFront methods, in addition to its expected 
> source data iteration duties. The reason I do this is because I 
> swear I read in a github discussion that front is expected to 
> be O(1), and the only way I can think to achieve this is to 
> stash the front element of a range in a private field; popFront 
> would thus also set this field to a new value upon every call, 
> and front would forward to it. (Or front would be the cache 
> itself.)
> At the moment, I feel that as long as the stashed front element 
> isn't too "big" (For some definition of big, I guess.), that 
> built-in caching should be fine. But is this acceptable? What's 
> the best practice for determining which range member should 
> perform what work? (Other than iterating, of course.)

It's a time-space tradeoff. As you say, caching requires 
additional space to store the cached element. On the other hand, 
*not* caching means that you spend unnecessary time computing the 
next element in cases where the range is only partially consumed. 
For example:

```d
import std.range: generate, take;
import std.algorithm: each;
import std.stdio: writeln;

generate!someExpensiveFunction.take(3).each!writeln;
```

Naively, you'd expect that `someExpensiveFunction` would be 
called 3 times--but it is actually called 4 times, because 
`generate` does its work in its constructor and `popFront` 
instead of in `front`.