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.)

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.)

In English, `front` is a noun, `popFront` have a verb in it, so you know who should do more work :-)

On Tuesday, 15 June 2021 at 04:43:38 UTC, jfondren wrote:
> Well, consider this program:
>
> ```d
> import std;
>
> struct Noisy {
>     int[] source;
>     int pops, fronts;
>     bool empty() { return source.empty; }
>     void popFront() { writeln("popFront #", ++pops); source.popFront; }
>     int front() { writeln("front #", ++fronts); return source.front; }
> }
>
> void main() {
>     iota(5).array
>         .Noisy
>         .filter!"a%2"
>         .each!writeln;
> }
> ```
>
> Out of [0,1,2,3,4], only 1,3 pass the filter.
> Noisy's front is called seven times, 2x for each filter success.
> Noisy's popFront is called five times, 1x for each source member.
>
> But if you slap a .cache (from std.algorithm.cache) before the
> .filter then these counts are the same.

Appreciate the response.
From your example, one solution is that perhaps documenting one's custom range type with a disclaimer that its front method is expensive upon invocation is reasonable; the consumer of the range type, given this information, might then determine whether using cache is appropriate for them.
I'm still left wondering whether one should strive for ensuring that front is O(1), and various solutions to this. With that said, I now realize my question is kind of ridiculous since the answer might be predicated upon other aspects: the type data being consumed; the common operations that are to be performed upon a custom range.

On Tuesday, 15 June 2021 at 04:57:45 UTC, mw wrote:
> In English, `front` is a noun, `popFront` have a verb in it, so you know who should do more work :-)

Sure, but, for example, the front method of Phobos' MapResult is the one applying the predicate to the source's front. There's a clear separation of responsibilities between popFront and front: the former iterates over the source, and the latter performs an operation that produces the range's elements.

On Tuesday, 15 June 2021 at 05:03:45 UTC, surlymoor wrote:
> On Tuesday, 15 June 2021 at 04:57:45 UTC, mw wrote:
>> In English, `front` is a noun, `popFront` have a verb in it, so you know who should do more work :-)
>
> Sure, but, for example, the front method of Phobos' MapResult is the one applying the predicate to the source's front. There's a clear separation of responsibilities between popFront and front: the former iterates over the source, and the latter performs an operation that produces the range's elements.


I think there is another convention (although it's not formally enforced, but should be) is:

-- `obj.front() [should be] const`, i.e. it shouldn't modify `obj`, so can be called multiple times at any given state, and produce the same result

-- `obj.popFront()` perform the actual mutation of the internal state the `obj`, each invocation will change the object's state once.


e.g.

https://dlang.org/library/std/range/primitives/front.html
the 2nd decl:
dchar front(T) (
  scope const(T)[] a
) pure @property @safe
if (isAutodecodableString!(T[]));

you can see `const`


but

https://dlang.org/library/std/range/primitives/pop_front.html
void popFront(C) (
  scope ref inout(C)[] str
) pure nothrow @trusted
if (isAutodecodableString!(C[]));

it's `ref inout`, which means the passed-in object is intended to be modified inside the method in-place.

On Tuesday, 15 June 2021 at 05:17:06 UTC, mw wrote:
> I think there is another convention (although it's not formally enforced, but should be) is:
>
> -- `obj.front() [should be] const`, i.e. it shouldn't modify `obj`, so can be called multiple times at any given state, and produce the same result
> -- `obj.popFront()` perform the actual mutation of the internal state the `obj`, each invocation will change the object's state once.

That's a separate matter. To use as an example once more, MapResult's front method produces the range's elements, and its invocation results in the identical element given that popFront isn't called; it doesn't affect the range's source. It satisfies those expectations, but it leaves wanting to know whether one should strive for front being inexpensive to call.
My original question is stupid, and I think I'm just going to have to experiment.

On 15.06.21 07:17, mw wrote:
> https://dlang.org/library/std/range/primitives/front.html
> the 2nd decl:
> dchar front(T) (
>    scope const(T)[] a
> ) pure @property @safe
> if (isAutodecodableString!(T[]));
> 
> you can see `const`
> 
> 
> but
> 
> https://dlang.org/library/std/range/primitives/pop_front.html
> void popFront(C) (
>    scope ref inout(C)[] str
> ) pure nothrow @trusted
> if (isAutodecodableString!(C[]));
> 
> it's `ref inout`, which means the passed-in object is intended to be modified inside the method in-place.

`const` and `inout` mean the same thing here: Both functions cannot modify the elements of the array.

The difference lies in `ref` alone. `front` receives a copy, so it can't change the length of the array you pass in. `popFront` receives by reference, so it can (and does).

On Tuesday, 15 June 2021 at 04:24:09 UTC, surlymoor wrote:
> 
> 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.)

The "general rule" is that `front` should return the same result on multiple calls until after the next call to `popFront`. I don't know of any requirement that such an operation be O(1), but the expectation is certainly there. The implication then is that any necessary work should be carried out in `popFront` to advance the range (and additionally in a constructor if things need to be teed up first) and that `front` should just return the current element.

On 6/14/21 10:17 PM, mw wrote:

> I think there is another convention (although it's not formally
> enforced, but should be) is:
>
> -- `obj.front() [should be] const`, i.e. it shouldn't modify `obj`, so
> can be called multiple times at any given state, and produce the same
> result

In other words, front() should be "idempotent".

To the OP, there is the following presentation that is related and touches on similar concerns:

  https://forum.dlang.org/thread/diexjstekiyzgxlicnts@forum.dlang.org

Ali