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
