On Sun, 03 Jan 2010 00:49:08 -0500, Andrei Alexandrescu
<[email protected]> wrote:
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.
Well, one thing you could do is:
enum thisIsAnInputRange = true;
and then no special implementation is needed for normal forward ranges.
the other point is there is no special treatment needed inside algorithms
-- the risk of forgetting to use save at the right points of the algorithm
is higher than forgetting to say isForwardRange!(R) at the beginning of
the function.
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.
Not having opSlice be part of the interface itself does not preclude it
from implementing opSlice, and does not preclude using ranges of it in
std.algorithm. If I'm not mistaken, all functions in std.algorithm rely
on compile time interfaces. opApply allows for full input range
functionality for things like copying and outputting where templates may
not be desired.
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?
Search and positioned removal are also a primitives, but not defined on
the interface. remove was a primitive on Tango's containers, and
dcollections was originally meant to be a replacement for Tango's
containers.
I think the point is, if you have an interface reference, what would be
the minimum functionality needed so that you could use a container without
knowing its implementation.
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.
Again, it's part of the minimal usable interface. It's not a generic
algorithm, because some containers can implement this more efficiently.
Plus, to use the generic algorithms, you would need to use interfaces as
ranges which I think are completely useless.
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.
All current dcollection containers have O(1) length.
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)?
first, dcollections' list implementation is doubly linked because all
collections are forward and backward iterable.
second, even for singly linked lists, you can have either O(1) length or
O(1) splicing (consuming a link list range into another linked list).
Dcollections' default link list implementation uses O(1) length since I
think splicing is a specialized requirement.
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.
How do you define that on Container(V)? on Map(K, V), set(K k, V v) is an
interface method.
what you can do is define Map(K, V) as inheriting Container(Tuple!(K, V)),
but then trying to use the container functions are very cumbersome. In
dcollections, Map(K, V) inherits Collection(V).
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.
No, you can easily write container-independent iteration as long as you
have the implementation.
If you use interfaces you can write opApply wrappers to do different
things. I'm not sure what you mean by composition.
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.
How is it more flexible? You can't replace data, and you can't remove
data while iterating, both of which are possible with dcollection's
primitives. If you have a Container(E) which defines InputRange!E
opSlice, how do you get at the more defined range definition? casting?
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.
Not having opSlice on the interface guarantees you never have a virtual
call for iteration :) opApply mitigates the virtual call on the interface.
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.
If the minimal container design isn't usable without std.algorithm, then I
don't think it's worth having interfaces. If you need std.algorithm, you
need the full implementation of the container because it's a compile-time
interface. Interface ranges are something that should be avoided, it's
like having a programming language where everything has to be a class.
What you are saying seems completely incorrect to me: "since not all
containers can implement fast search, I'm going to guarantee that *all*
containers use a linear search via their interface. *AND* I want to make
each loop in the search algorithm call 3 virtual functions!" How is that
better than a search function that guarantees linear performance but gives
the option of being as fast as possible with no loop virtual calls? In
fact, my implementation is guaranteed to be faster than std.algorithm
because of the lack of virtual calls.
-Steve
