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

Mon Dec 26 04:08:36 CET 2005

At 09:10 PM 12/25/2005 -0500, Martin Blais wrote:
>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.

Since I routinely use 2-item tuples (twoples?) as cons cells when I 
actually need a linked list, I think I'm in a good position to say that 
this isn't true. Certainly it's not true for me.
Since Python effectively has single-character operations for both consing 
and car/cdr (a ',' on the right or left sides of an assignment statement 
respectively), as well as trivial truth testing for () as a "nil", suggests 
to me that anybody who wants a lispy list can easily have one. For any 
application where such a structure excels (like shared sublists/trees and 
recursive traversals), it's so darn easy to use them in Python that I don't 
think anything special is needed.
Honestly, ISTM that the One Obvious Way to do lispy lists in Python is to 
just use two-tuples, with no special library functions. Sequence packing 
and unpacking is extremely fast in Python, too, probably faster than any 
method calls to a more heavyweight builtin type could be.
Thus, I'm -1 on creating another cons type. Why do this:
 foo = cons(bar, None)
 car_foo = foo.car
 cdr_foo = foo.cdr
when you can just do this:
 foo = bar, ()
 car_foo, cdr_foo = foo
How much simpler can you get?