Book in the works by Alexander Stepanov

[Alix Pexton]

Bill Baxter wrote:
> On Sat, Sep 6, 2008 at 3:01 PM, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>> See http://www.stepanovpapers.com/eop/eop.pdf for an interesting read. The
>> school of thought put forth by Stepanov resolves the recent digitalmars.d
>> debate on interface design (e.g. whether opIndex should be part of a list
>> interface) by favoring designs that define primitive efficient operations
>> from which others, potentially less efficient, can be derived. On pages 5-6:
>>
>> "A computational basis for a type is a finite set of procedures that enable
>> the construction of any other procedure on the type. A basis is efficient if
>> and only if any procedure implemented using it is as efficient as an
>> equivalent procedure written in terms of an alternative basis. For example,
>> a basis for unsigned 32-bit integers providing only zero, equality, and the
>> successor function is not efficient since the implementation of addition in
>> terms of successor is linear."
> 
> Just to clarify:  you mean that Stepanov's answer is that there should
> not be any method to obtain the nth item in a linked list because it
> is not a fundamental operation?  Because it can be synthesized using a
> sequence of calls to "next()"?
> 
> That may be, but without reading the whole thing, it's not really
> clear from just the above quote that Stepanov is advocating that
> anything not in the basis should not be in a class.
> 
> Even if that is what he advocates, then surely he doesn't go so far as
> to advocate that a library should not provide *any* operation that a
> user can write themselves in an efficient way.  A major point of a
> library is to provide common operations on data types.
> 
> So in that case I don't really see how Stepanov resolves the debate
> about using opIndex for a list.  He says opIndex/nth is not part of
> the type's basis, but he doesn't say you shouldn't have an nth
> function.  So maybe he claims it should be a free function outside the
> class, in which case the question is trivially resolved for the case
> of D since D doesn't allow operators to be defined outside a class
> right now.   But that kind of answers it with a technicality.  It
> doesn't answer the real question being debated here of whether
> offering an opIndex is an implicit promise of a fast indexing
> operator.
> 
> Or maybe your point was that Stepanov says O(n) linear search *is*
> fast for a linked list because it's as fast as it can be given the
> linked list basis?  So then it should be ok to use opIndex?
> 
> --bb

I think the way toapply this the the Linked List opIndex debate is to say
that:

The most efficient way to implement opIndex(n) for a linked list is to call next()
n times where next() is a procedure that is accepted as a part of List's basis (or
the node's, or the iterator's.)
As that opIndex() would be composed of only procedures from the basis, it is not a
part of the basis itself.

If you really need to get the nth item in your list then you can write your own
procedure, because the basis for the List contains the procedures needed, i.e. Next.

If I find myself needing to regularly get the nth item from a linked list I would
start to ask myself why I was using a list in the first place.

A...