output ranges: by ref or by value?

[Andrei Alexandrescu]

Steven Schveighoffer wrote:
> My theory is, given this list of ranges, if you pair them with an 
> algorithm that requires save capability, you wouldn't want to use that 
> algorithm on it anyways (kinda like the consume example).

Why gratuitously limit the design? You're asking to replace this:

R save() { return this; }

with:

enum thisIsAForwardRange = true;

Is there a reason? The former leaves in flexibility. The latter doesn't, 
for no good reason.

>> Struct ranges won't work with a container hierarchy. If you define a 
>> container hierarchy (classes etc.) you'll also need a range hierarchy. 
>> Otherwise defining the inheritance relationship is impossible. Consider:
>>
>> abstract class Container(E) { // most general container
>>      @property bool empty();
>>      bool add(E element);
>>      E removeAny();
>>      InputRange!E opSlice();
>> }
>>
>> That's what I'd expect any container worth its salt to implement: (a) 
>> test for empty; (b) add an element to the container; (c) remove some 
>> element from the container; (d) get a range that spans the entire 
>> container. (Probably removeAll() and a range-positioned remove() would 
>> make sense, too.)
> 
> The range interface is compile-time only, there is no need to define it 
> in the container interface.  opSlice does not need to be part of the 
> interface, even if it is defined on all the container types.
> 
> opApply makes for a much better interface-friendly iteration anyways.

I want container users to be able to save iteration state and also to 
open up containers to std.algorithm and other goodies, so I'm shying 
away from opApply.

> BTW, the primitives in dcollections are:
> 
> clear(); // clear all elements
> remove(V v); // remove an element

Search and remove? That's an odd primitive. Why wouldn't you offer an 
interface for iteration that allows an algorithm for search, and a 
primitive for positioned removal?

> contains(V v); // returns whether an element is contained in the colleciton

I don't think this belongs to primitives. It's O(n) for many containers 
and again it's a generic algorithm, not a member.

> length(); // the length of the collection

That's not a primitive either. std.algorithm.walkLength is. For me, all 
sorts of red flags and alarm buzzers go off when primitives are 
guaranteed that can't be implemented efficiently but by a subset of 
containers. You can't discount complexity as a implementation detail.

> dup(); // duplicate the collection
> opApply(int delegate(ref V v) dg); // iterate the collection
> opApply(int delegate(ref bool doPurge, ref V v) dg); // purge the 
> collection
> 
> That means it covers only empty in your list of must-have functions (via 
> length() == 0).

How do you implement length() for a singly-linked list? Is empty() going 
to take O(n)?

> Add is not a primitive because the Map collections 
> shouldn't assign some random key to the new element.  removeAny is 
> defined only on sets and multisets, but I'm not sure that it couldn't be 
> moved to Collection, in fact, I'll probably do that.

add is a primitive that takes Tuple!(K, V) as the element type.

> Note that it's missing begin and end which are defined on every single 
> container type (i.e. the equivalent of the all-elements range).  This is 
> because those primitives return a struct that is different for every 
> container type.

So you can't write container-independent iteration code unless you use 
opApply, in which case composition becomes tenuous.

> It also surpasses opSlice via opApply, since all an input range can do 
> anyways is iterate.  In fact, opApply is more powerful because you can 
> change elements and remove elements (via purging).  Plus it's more 
> efficient than a range-via-interface.

An input range is a subset of other (more powerful) ranges. It's also 
much more flexible. I agree that calling range primitives via interfaces 
can become an efficiency liability.

>>> I see a range as being useful for iteration or algorithms, but not 
>>> for general use.  A great example is AAs.  Would you say that an AA 
>>> *is* a range or should *provide* a range?  If it is a range, does 
>>> that mean you remove elements as you call popFront?  Does that make 
>>> any sense?  If it doesn't, then what happens if you add elements 
>>> through another alias to that AA?
>>
>> An AA provides several ranges - among which byKey and byValue.
> 
> I misunderstood your statement "[a container hierarchy] does need range 
> interfaces."  I thought you meant containers themselves need to 
> implement the range interface, I see now that isn't the case, so my bad.

Yah, they'd offer it as a result of opSlice(). Covariant return types 
will ensure there's no virtual call when you know what container you 
operate on.

Above all: the primitive set for a container must be a small set of 
functions that (a) can be implemented by all containers within 
reasonable efficiency bounds, and (b) are container-specific, not 
generic. IMHO any container design that defines a search(Element) as a 
primitive is misguided. Searching is not a container primitive - it's an 
algorithm. Only more specialized containers (e.g. trees, hashes etc.) 
can afford to define search(Element) as a primitive. Linear search is a 
generic algorithm that works the same for everyone. It does not belong 
as a method of any container.


Andrei