Transient ranges

[Steven Schveighoffer via Digitalmars-d]

On 5/31/16 10:46 AM, Dicebot wrote:
> On Monday, 30 May 2016 at 12:53:07 UTC, Steven Schveighoffer wrote:
>> On 5/30/16 5:35 AM, Dicebot wrote:
>>> On Sunday, 29 May 2016 at 17:25:47 UTC, Steven Schveighoffer wrote:
>>>> What problems are solvable only by not caching the front element? I
>>>> can't think of any.
>>>
>>> As far as I know, currently it is done mostly for performance reasons -
>>> if result is fitting in the register there is no need to allocate stack
>>> space for the cache, or something like that. One of most annoying
>>> examples is map which calls lambda on each `front` call :
>>> https://github.com/dlang/phobos/blob/master/std/algorithm/iteration.d#L587-L590
>>>
>>
>> Maybe my understanding of your post is incorrect. You said "It is
>> impossible to correctly define input range without caching front which
>> may not be always possible and may have negative performance impact."
>>
>> I'm trying to figure out which cases caching makes the solution
>> impossible.
>
> There are two separate points here:
>
> 1) Current definition of input range (most importantly, the fact `front`
> has to be @property-like) implies `front` to always return the same
> result until `popFront` is called.

Regardless of property-like or not, this should be the case. Otherwise, 
popFront makes no sense.

> 2) For ranges that call predicates on elements to evaluate next element
> this can only be achieved by caching - predicates are never required to
> be pure.

Or, by not returning different things from your predicate.

This is like saying RedBlackTree is broken when I give it a predicate of 
"a == b".

> 3) But caching is sub-optimal performance wise and thus bunch of Phobos
> algorithms violate `front` consistency / cheapness expectation
> evaluating predicates each time it is called (liked map).

I don't think anything defensively caches front in case the next call to 
front is different, unless that's specifically the reason for the range.

>>> I don't really care about concept of transient ranges, it is the fact
>>> there is no guarantee of front stability for plain input ranges which
>>> worries me.
>>
>> But this is inherent in languages which support mutable data. If you
>> want data that doesn't change, require copied/unique data, or
>> immutable data.
>
> This has nothing to do with mutability, look at this totally broken
> example:
>
> import std.random;
> import std.algorithm;
> import std.stdio;
> import std.range;
>
>
> void main ( )
> {
>     auto range = only(0).map!(x => uniform(0, 10));
>     writeln(range.front);
>     writeln(range.front);
>     writeln(range.front);
> }
>

I think we should be aware that the range API doesn't prevent bugs of 
all kinds. There's only so much analysis the compiler can do.

-Steve