Truly lazy ranges, transient .front, and std.range.Generator

[Joseph Rushton Wakeling via Digitalmars-d]

Hello all,

One of the design considerations I've been mulling over recently, in terms of 
random number generation functionality, is that while we talk of ranges being 
lazily evaluated, in fact this isn't strictly true.

Most ranges are in fact a mix of lazy and eager: lazy in their use of popFront, 
but eager in that the current value of .front is always pre-calculated, usually 
starting with the first value being calculated in the constructor.  This is fine 
for many ranges, whose outcome is in any case deterministic, but it's not 
appropriate for many other cases, where the appropriate moment of evaluation of 
'front' is arguably _the moment where front is called_.

This kind of requirement clearly holds anywhere where the values of the range 
depend on some kind of external input, and that arguably should include things 
like sources of randomness (even if they are, under the hood, only pseudo-random).

One possible support for this is given by std.range.Generator, which implements 
a very simple wrapper of a callable entity via the following range primitives:

     enum empty = false;

     auto ref front() @property
     {
         return fun();
     }

     void popFront() { }

Now, first, I should say that I think this is a good example of how the 
classification and concept of ranges is incomplete -- there is a case for an 
even simpler range than InputRange, one which _just_ has .empty and .front 
defined, and which we might call a TransientRange -- but second, it's 
problematic, inasmuch as it's an incomplete solution to the problem of truly 
lazy ranges.

In some cases we're going to want true laziness of evaluation, but _not_ 
transience of .front.  In these cases, the _first_ time .front is called, its 
value should be freshly evaluated; but thereafter, the value is cached, until 
.popFront() is called, at which point .front will be re-evaluated lazily the 
next time it's called.  Something like std.algorithm.cache is inappropriate 
here, precisely because it's eager in its calculation of the cached values.

As far as I can see, we don't have a valid solution for this case.  We have some 
functionality in std.random -- e.g. randomCover and randomSample -- which 
implements rather shaky workarounds for that lack.

I can't imagine this isn't a known case/problem, but as far as I can see any 
discussion of it has been more on GitHub than here.  So before rushing off with 
Yet Another Custom Solution, I thought I'd raise the issue here, to ask what the 
current state of thought is on these kinds of challenge, and what may be 
upcoming in people's roadmaps.

Thanks & best wishes,

     -- Joe