Steven Schveighoffer wrote:
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.
isForwardRange will be defined to yield true if and only if the range
defines save. But I see you point - user code only asserts
isForwardRange and then does not bother to use save(), just copies stuff
around in confidence that copying does the right thing.
Thanks for this insight. I don't see how to reconcile that with class
ranges and covariance.
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.
The point is how much container-independent code can someone write by
using the Container interface. If all you have is a Container, you can't
use it with any range algorithm.
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.
Yes, and I think remove(V v) does not belong to the minimum
functionality. It combines two functions (search and remove) and raises
questions such as what happens to duplicate elements.
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.
But this is exactly what I believe to be a mistake: you are abstracting
away algorithmic complexity.
Plus, to use the generic algorithms, you would need to use interfaces as
ranges which I think are completely useless.
Why?
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.
Some containers can't define O(1) length conveniently.
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.
Right. The question is how much pressure Container is putting on the
implementation. I'd rather leave it to the list implementation to decide
to store the length or not.
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.
Map!(K, V) has Tuple!(K, V) as its element type.
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.
In this context: container-independent = using the Container interface.
This is the whole purpose of creating a container hierarchy. If the
container design fosters knowing the implementation, maybe a class
hierarchy is not the right choice in the first place.
If you use interfaces you can write opApply wrappers to do different
things. I'm not sure what you mean by composition.
For example, compose ranges a la retro or take.
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?
You can replace data by assigning to range's elements. Removal is done
via positioned remove (which I think needs to be a primitive).
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.
And takes away the ability to compose ranges and to use algorithms with
the container.
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.
Why?
I think the other way: if the minimal container design is unusable with
std.algorithm, the design took a wrong turn somewhere.
If you need std.algorithm,
you need the full implementation of the container because it's a
compile-time interface.
How did you reach that conclusion? std.algorithm uses a syntactic
interface that is obeyed by interfaces too. There's no problem.
Interface ranges are something that should be
avoided, it's like having a programming language where everything has to
be a class.
I disagree. The negation of an implementation dogma can be just as
limiting as the dogma. The way I see it, a design defines some
desiderata. Then it does whatever it takes to fulfill them.
If one desideratum is to use a class hierachy to write
container-independent code, then interface ranges naturally follow.
There's no ifs and buts about it.
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.
This is a misunderstanding. In the STL linear containers don't define
find(), but associative containers do. That is the correct design.
*AND* I want to
make each loop in the search algorithm call 3 virtual functions!"
Not necessarily. This happens only if you use the Container interface to
write container-independent code. It is the cost it takes for the design
to fulfill its desiderata.
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?
It is better because it doesn't write off search complexity as an
implementation detail. "Linear or better" is not a good guarantee. A
good guarantee is "From this node of the hierarchy down, this primitive
is defined to guarantee O(log n) search". Linear search is a generic
algorithm and does not belong to any container.
Andrei
