[Python-Dev] deque alternative (was: Linked lists)

[Martin Blais]

On 12/25/05, Christian Tismer <tismer at stackless.com> wrote:
> Guido van Rossum wrote:
>
> > Python's philosophy about (built-in) data types, inherited from ABC,
> > is to offer a few powerful clearly distinct choices rather than lots
> > of alternatives with overlapping usages. This reduces the time it
> > takes to choose a data type and reduces the risk of picking the wrong
> > type. (You seem to be indicating that this is indeed what's happening
> > to you in Lisp. :-)
>
> Speaking about the new dequeue type, I have the impression that
> this reasoning applies there a bit, too?
> Dequeues of course have applications, and I saw them used,
> especially by newcomers to the language. So I like their
> functionality.
>
> But actually, I'm not so convinced if we need to introduce
> a new datatype. How about an extension to normal lists
> that does a little tracking of use-cases and decides about
> changing its implementation upon the presence of inserts/deletes
> at the lower end of the list?
>
> I'm btw. not sure if this raises an implicit/explicitiness issue.
> My question is if it is necessary to put the burden about explicitly
> choosing a specialized two-ended list on the programmer, or if it
> is simple enough to make lists just do the right thing, if lists
> are used in a dequeue-style manner. Or is this maybe too much magic
> happening?

IMO it's a little bit too much magic.  Plus, if you pass these
instances around e.g. between libraries, how could you determine with
certainty the usage patterns without analysing the entire codebase?  I
think the user has to be involved.

A problem I see now is that there is no way for me to
indicate--whether there currently exists or not an appropriate data
type with the desired characteristic-- whether I want an array (Python
list) or a real list, both of which are really, really basic
fundamental kinds of data structures with very different complexity
characteristics.  The source code I write does not carry this
information and therefore if in the future it would become available
there won't be an easy way to convert code to take advantage of this. 
This choice, is being made in the programmer's head, but the
distinction blurred in the source code because lists are just not
there.

I still haven't had time to cook a proper reply to Guido, but one
thing I see is that many ppl on the list seem to think that because
there aren't many use cases (that they can see), therefore there isn't
much use for a list collection type.  I would instead argue that
because the list type has never been available, people have gotten
used not to use them, and therefore settle with arrays and do not see
a need for them.  When all you have is a hammer, everything seems to
be a nail.  When you don't have lists, you make do with arrays and you
think it's ok (and it pretty much is, in the sense that Python, at
least compared to C/LISP, is very slow, so it for the kinds of things
you use it for, it does not matter all that much).  When you're used
to having lists available, you miss being able to express that the
data structure you want should have the characteristics of a list,
with the intended performance characteristics.  Being able to select
between a list and an array is like having a bit more vocabulary in
natural languages.

I would agree with the use case condition if we were talking about a
very domain-specific collection type, but we're talking about lists
here... it's really fundamental stuff...

Also, there is something incredibly elegant and simple and compact
about the cons cell, maybe all we need is a good simple cons cell type
and a nice interface on it, so you get both single-linked lists and
trees at the same time...

(more after the xmas thing has passed)