cache() method - should it cache on popFront() or on first call to front()

[Dukc]

On Monday, 10 February 2020 at 10:43:33 UTC, Piotr Mitana wrote:
> I have recently found std.algorithm.iteration.cache() 
> function's behavior a little bit confusing. I'll demonstrate it 
> with this example:
>
> void main()
> {
>     auto arr = sequence!"n"
>         .map!(n => { writefln("Mapped: %d", n); return n; }())
>         .cache
>         .until(3, No.openRight)
>         .array;
>
>     arr.writeln;
> }
>
> What would you expect such a code to write? Actually what it 
> writes is:
>
> Mapped: 0
> Mapped: 1
> Mapped: 2
> Mapped: 3
> Mapped: 4
> [0, 1, 2, 3]
>
> What was unexpected to me is that it still passed 4 to map 
> function despite the fact that I should be left out by until. 
> Later I have read that range's element is calculated eagerly 
> when the popFront() is called.
>
> However, when the until() is called immediately after, there is 
> element is calculated needlessly. This could be avoided by 
> caching not when popFront() is called, but when front() is 
> called for the first time of the new element.
>
> I solved the problem with the following simple template:
>
> auto cacheOnAccess(Range)(Range source) if(isInputRange!Range)
> {
> 	struct CacheOnAccess
> 	{
> 		Range source;
> 		Nullable!(ElementType!Range) cachedFront;
>
> 		this(Range source)
> 		{
> 			this.source = source;
> 		}
>
> 		@property ElementType!Range front()
> 		{
> 			if(cachedFront.isNull)
> 				cachedFront = source.front.nullable;
>
> 			return cachedFront.get;
> 		}
>
> 		@property bool empty()
> 		{
> 			return source.empty;
> 		}
>
> 		void popFront()
> 		{
> 			source.popFront();
> 			cachedFront.nullify();
> 		}
> 	}
>
> 	return CacheOnAccess(source);
> }
>
> Maybe a change in Phobos could be considered - either adding a 
> parameter to cache() template, so that the moment of caching 
> could be determined? Alternatively, another function could be 
> added, which would cache when the element is accessed for the 
> first time.

Sounds good. std.range.tee[1], which also always executes the 
function only once for each element, already does this. By 
default it executes on popFront() (but on popped value, not the 
new one, which frankly is surprising at least for me), but it has 
PipeOnPop flag which, if set to no, executes on first invocation 
of front. If we follow this example, it means adding a template 
parameter.

1: https://dlang.org/phobos-prerelease/std_range.html#tee