Proposal: add list.popend() method
Terry Reedy
Proposal: add [].popend() method so lists can be used as stacks 'as-is',
out of the box (or now, off the net!).
Stacks need two basic functions: push() and pop().
is-empty() and top() are nice auxiliaries.
Given stack s = [] (initially), we push with built-in .append(value).
Or we can bind the method to s with s_push=s.append and just write
s_push(value).
Is-empty() is not necessary since, in the context of a conditional test,
s tests false or true as appropriate.
Top() is s[len(s)-1] or, more compactly, s[-1:].
So only pop() is missing as a built-in facility.
One can write it in-line
var = s[-1:]; del s[-1:] # or use len(s)
or as a function (which is so short, that it is not, as far as I know,
in any of the standard libraries)
def pop(s):
if type(s) != type([]): raise TypeError # test is easy to forget about
i = len(s)-1
tem = s[i] # let empty list index error prop
del s[i]
return tem
If [].pop() or popend (in analogy with append) were added as a list
method:
1. there would be no possibility of users mis-coding.
2. there would be no need to try to think of where it could go in either
the standard or private libraries. (Being the the only stack function
that is missing, it is sort of an orphan.)
3. the syntax for pushing and poping would be the same (now we have
s.append(v) to push but pop(s) to pop.)
4. popend(), written in C, would be about as fast as append(). This
would, for instance, make explicit-stack-based parsing at least a bit
faster.
5. we could could advertise that Python's built-in lists also serve as
built-in stacks -- without having to add 'if you program the missing pop
function yourself'.
Objections (and responses):
1. it is not necessary -- neither is the new {}.get()
2. we have managed without it -- as we have with {}.get()
3. it is creaping featurism -- no, pop() is as basic as get()
Both will/would be useful and heavily used.
4. will it break existing code? - No, it will go into the write-only
list-attribute namespace which users cannot modify, and therefore have
not in existing code.
Terry J. Reedy
M.-A. Lemburg
Terry Reedy wrote:
>
> Proposal: add [].popend() method so lists can be used as stacks 'as-is',
> out of the box (or now, off the net!).
Why would you want to emulate a stack with a list ? A much more
generic data type (which can internally use all the benefits
of the simple structure) would give you better performance and
make the difference between lists (random access) and stacks
(LIFO access only) much clearer.
Try this one:
class UserStack:
def __init__(self):
self.stack = ()
def push(self,x):
self.stack = (x,self.stack)
def pop(self):
x, self.stack = self.stack
return x
def is_empty(self):
return len(self.stack) == 0
def top(self):
return self.stack[0]
def __len__(self):
i = 0
s = self.stack
while len(s) != 0:
s = s[1]
i = i + 1
return i
[Can't remember who actually had this tuple idea... it
wasn't me, that's for sure :]
Note that that small tuples (this class only uses 0-
and 2-tuples) are kept on a free list, so only very few
mallocs are needed, making it actually quite fast.
If I find some time (maybe around christmas or on a lazy
afternoon), I'll code this up in C, along with the standard
data type queue (FIFO). [That's why I named the class UserStack]
--
Marc-Andre Lemburg
John (Max) Skaller
On Sat, 22 Nov 1997 14:01:09 GMT, lem...@rz.uni-duesseldorf.de wrote:
>Terry Reedy wrote:
>>
>> Proposal: add [].popend() method so lists can be used as stacks 'as-is',
>> out of the box (or now, off the net!).
>
>Why would you want to emulate a stack with a list ?
>class UserStack:
Yes, it would. But the result isn't a list.
There are places where you need an actual list.
There are others where a sequence is enough
(the UserStack class isn't a sequence, but it
could be extended to be one by delegation)
So it isn't clear which is the better method.
(This is an instrinsic problem with OO)
John Max Skaller ph:61-2-96600850
mailto:ska...@zip.com.au 10/1 Toxteth Rd
http://www.zip.com.au/~skaller Glebe 2037 NSW AUSTRALIA
Mike Meyer
In <347739e5....@news.zip.com.au>, ska...@zip.com.au (John (Max) Skaller) wrote:
> On Sat, 22 Nov 1997 14:01:09 GMT, lem...@rz.uni-duesseldorf.de wrote:
> Yes, it would. But the result isn't a list.
> There are places where you need an actual list.
>
> There are others where a sequence is enough
> (the UserStack class isn't a sequence, but it
> could be extended to be one by delegation)
>
> So it isn't clear which is the better method.
> (This is an instrinsic problem with OO)
While I personally like the idea of a .pop method for lists, it seems
to violate one of the design principles that Guido uses: that methods
either modify objects, or return values from/about it, but not both.
If you don't allow a method to do both, then you need two operations,
and we already have those as single statements/expressions:
Top of stack == list[-1]
Unstack element == del list[-1]
<mike
--
Do NOT reply to the address in the From: header. Reply to mwm instead of
bouncenews at the same machine. Mail to bouncenews will be returned with
instructions on reaching me. Sending unsoliticed email I consider commercial
gives me permission to subscribe you to a mail list of my choice.
Michael W. Ryan
tjr...@udel.edu (Terry Reedy) writes:
> Proposal: add [].popend() method so lists can be used as stacks 'as-is',
> out of the box (or now, off the net!).
But then you're confusing the issue of what a list is. You're
combining a list with a stack. If you need a stack, you should
create/use a stack class. The fact that a Python list can be used as
a stack is more serendipity than deliberate design, I think.
--
Michael W. Ryan
Email: mr...@netaxs.com WWW: http://www.netaxs.com/~mryan/
PGP fingerprint: 7B E5 75 7F 24 EE 19 35 A5 DF C3 45 27 B5 DB DF
PGP public key available by fingering mr...@unix.netaxs.com (use -l opt)
John (Max) Skaller
On Sat, 22 Nov 1997 12:18:53 PST, wrote:
>While I personally like the idea of a .pop method for lists, it seems
>to violate one of the design principles that Guido uses:
Alex Stepanov use that same principle designing STL.
>that methods
>either modify objects, or return values from/about it, but not both.
>If you don't allow a method to do both, then you need two operations,
Perhaps the set of "principles" can be extended.
In practice, STL was modified by the C++ committee away from
Stepanov's original design for two reasons:
1) It wasn't very convenient for users
2) It was extremely inefficient!
So I'd guess the principles need to be adjusted
something like:
1) Accessors (don't change anything)
2) Mutators -- return information
about the change (delta)
That would mean that "pop" would be OK:
even though it might be implemented as two
operations:
def pop(x):
tmp = x[0]
del x[0]
return tmp
it would be regarded as an atomic
"mutate and return delta" operation.
The rule would be not to return information
which was invariant -- the same before
and after the change.
Comments?
Terry Reedy
REPONSE TO COMMENTS (as of Sunday)
Michael W. Ryan:
> you're confusing the issue of what a list is.
Which 'list' definition are you referring to? Python? (interface or
implementation?). Lisp? Computer science? (again, i or i?) Dictionary?
A list, to me, for present purposes, is an mutable sequence of items.
In terms of implementation, a Python list is not a traditional CS
(linked) list at all, but an (elastic) array with an automatic and
hidden resizing (and copying) mechanism. I found this confusing at
first, and hesitated in adopting Python until I understood that I would
still be able to access and replace list (array) elements in constant
rather than linear time.
> You're combining a list with a stack.
What do you mean by 'combining'? A stack is a list with a particular
access protocol. They are already 'combined' in this sense,
irrespective of anything I say.
> If you need a stack, you should create/use a stack class.
Why? Why not add the one missing piece needed to directly use Python's
elastic arrays as a stack! -- without easy but annoying extra coding.
There are three traditional implementations for a stack: linked list,
fixed-size array large enough to accomodate the maximun expected size,
and variable-size array with the auxiliary data and methods needed to
prevent overflow by enlarging instead. Since Python's 'lists' are the
last of these three, why not use it and be upfront about it.
> The fact that a Python list can be used as a stack is more serendipity
than deliberate design, I think.
It is a *consequence* of the fact that a stack is a type of list. Any
list implementation with easy access to one end of the list (and what
implementation does not have such) can easily be used as a stack by
pushing to and popping from that end of the list.
The fact that only one more piece is needed is a consequence of
the fact that Guido choose to gives lists an append() method. I am just
proposing to add the inverse of append. Pretty sensible, in my view.
=======================================================================
Marc-Andre Lemburg:
>Why would you want to emulate a stack with a list?
Emulate? Python's elastic arrays (lists) are (or at least can be
regarded as) stacks with added functionality.
> A much more generic data type (which can internally use all the
> benefits of the simple structure) would give you better performance
Are you claiming that your tuple-stack .push() method, as a method
needing two dictionary lookups and an allocate, is faster than
.append()ing to a list with at least one empty slot? Have you data?
And would your pop() be faster than an as yet unwritten C-coded list
popend? Is this, or anything like it delivered with the standard
configuration?
> and make the difference between lists (random access)
> and stacks (LIFO access only) much clearer.
Traditional CS (linked) lists have sequential, not random access.
Random access is a feature of arrays and vectors, which is why I found
the Python use of 'list' for dynamically sized array to be initially
confusing.
Leaving this aside, would you favor deleting append() since it is a
stack-like LIFO operation rather than a randon-access operation? I am
only proposing to add its inverse. The confusion, if any, comes from
the presence of append withoug its inverse, and not the proposed
addition of the the latter.
> class UserStack {code deleted}
Your nested (recursive) tuple stack implementation is an interesting
version of a singly-linked list with single-end access. (& see below).
Directed-graph trees are an obvious and easy extension. The usage and
power of deeply nested tuples (and lists, for mutable versions) could
stand more promotion. Most examples of tuple/list usage are pretty
flat.
=====================================================================
John Max Skaller:
> {referring to Lemberg's stack class} Yes, it would.
I presume, be faster. Maybe, with some or all versions and compilers?
> But the result isn't a list. There are places where you need an
> actual list. There are others where a sequence is enough
> (the UserStack class isn't a sequence, but it could be extended
> to be one by delegation)
UserStack is not a sequential-slot-in-memory sequence/list but, as I
note above, it is a linked list: each node (tuple) has a value and a
reference to the next node (rest of list). (Yes, a couple of methods
could be added, such as non-destructive tail() or rest().)
For non-destructice sequential access, once could either add a
__getitem__ method that uses an added current-node attribute or define a
separate class of UserStack iterators, each instance of which would have
such an attribute. (Is this what you mean by delegation? I'm not
familiar with the term in this context.)
> So it isn't clear which is the better method.
> (This is an instrinsic problem with OO)
I am not claiming that append and its inverse popend (whether simulated
or built-in) are the best possible push and pop. I am claiming that they
are so used already, that this is a good use, and that it would be an
easy and obvious improvement to make popend an explicit builtin, and
that this would make Python even more attractive to newcomers who want
to use what they already know and be immediately productive.
======================================================================
Mike Meyer:
> While I personally like the idea of a .pop method for lists,
I glad someone is willing to say so.
>... it seems
> to violate one of the design principles that Guido uses: that methods
> either modify objects, or return values from/about it, but not both.
> If you don't allow a method to do both, then you need two operations,
> and we already have those as single statements/expressions:
If everyone adheared strictly to these principles, then no one could
ever write a proper stack or queue type or class. Should we reject
Lemberg's UserStack because of its 'violation'?
The current situation violates the design principle of pairing a
function and its inverse (when it exists and is separate). Thus, Python
has +/-, *//, exp/log, sin/asin (etc), frexp/ldexp, open/close, =/del
(bind/unbind), tuple()/list(), upper/lower, split/join, atoX/str,
but append/{missing}. I consider this principle important and this
violation thereof bothersome.
====================================================================
SUMMARY:
'Confusion' strikes me as a red-herring objection. To the extent
actually present, it is not a result of my proposal and would not be a
result of adding explicit inverse append(). 'List' has various common
and technical definitions. A PyList is what it is and what we make it
to be and does not have to exactly conform to any other particular
definition. I am glad that a PyLists are not what I initially thought
they were, but something better for most uses.
Though append() is convenient and popend() would be, neither is
necessary (given the other PyList syntax facilities).
L.append(v) can be written as L[len(L):]=[v]. Having append() saves
about 5 keystrokes (if L is a long expression, one could write t=L;
t[len(t):]=v, where 't' is some available short name), some processing
time, and the bother of remembering the exact expansion. (The similar
L=L+[v] is different since it rebinds L to a new list object instead of
extending it in place.)
v=L.popend() would similarly abbreviate v=L[-1]; del L[-1], with similar
effects. It would also fill in a bothersome 'hole' (the missing inverse
of append(). (The recently-added unnecessary-but-convenient list() did
the same relative to tuple()).
Finally, I believe that the addition of popend() to be as justifiable as
that of list(tuple) (1.4) and dict.get() (1.5). All three are
unnecessary but convenient. I expect popend() would be used more often
than list(), though possibly less than get(). I expect that it would do
more than either in making Python as-delivered more attractive to
prospective newcomers.
Terry J. Reedy
Paul Prescod
Terry Reedy wrote:
> Finally, I believe that the addition of popend() to be as justifiable as
> that of list(tuple) (1.4) and dict.get() (1.5). All three are
> unnecessary but convenient. I expect popend() would be used more often
> than list(), though possibly less than get(). I expect that it would do
> more than either in making Python as-delivered more attractive to
> prospective newcomers.
I have written the small stack before myself and although it did not
occur to me at the time that the list should do that itself (or perhaps
I forget that it did), your argument about symmetry seems compelling to
me. Append can easily be simulated with concatenation and popend with
read/truncate. One seems to have as much right as the other to exist.
Paul Prescod
Michael W. Ryan
tjr...@udel.edu (Terry Reedy) writes:
> Michael W. Ryan:
>
> > you're confusing the issue of what a list is.
>
> Which 'list' definition are you referring to? Python? (interface or
> implementation?). Lisp? Computer science? (again, i or i?) Dictionary?
Python. The interface. This is what most Python users will see.
> A list, to me, for present purposes, is an mutable sequence of items.
Which it is.
[snip]
> > You're combining a list with a stack.
>
> What do you mean by 'combining'? A stack is a list with a particular
> access protocol. They are already 'combined' in this sense,
> irrespective of anything I say.
So's a string.
> > If you need a stack, you should create/use a stack class.
>
> Why? Why not add the one missing piece needed to directly use Python's
> elastic arrays as a stack! -- without easy but annoying extra coding.
Because it keeps the builtin object straight-forward. Remember, part
of the Python's design is to keep the language and it's elements
fairly straight-forward, or least I always thought so. I think by
making lists explicitely a stack as well as a list, you're blurring
the distinction.
Allow me to point out that I'm approaching this from the perspective
of a user of Python, not crawling around in its internals.
> There are three traditional implementations for a stack: linked list,
> fixed-size array large enough to accomodate the maximun expected size,
> and variable-size array with the auxiliary data and methods needed to
> prevent overflow by enlarging instead. Since Python's 'lists' are the
> last of these three, why not use it and be upfront about it.
You've sort of answered your question here by you opening statement:
there are three ways to implement a model of a stack. Remember, all
OO designs are *models*. Models, definition, only implement those
features of reality that are important and in a way that is
important. To give a non-computer analogy: model cars (the plastic
kind that sit on your shelf for display) don't have working engines
because they're not supposed to be working cars, just visual
representations.
> The fact that only one more piece is needed is a consequence of
> the fact that Guido choose to gives lists an append() method. I am just
> proposing to add the inverse of append. Pretty sensible, in my
> view.
The append() method is simply a commonly-used special case of
insert().
> =======================================================================
>
> Marc-Andre Lemburg:
[snip]
> > A much more generic data type (which can internally use all the
> > benefits of the simple structure) would give you better performance
>
> Are you claiming that your tuple-stack .push() method, as a method
> needing two dictionary lookups and an allocate, is faster than
> .append()ing to a list with at least one empty slot? Have you data?
> And would your pop() be faster than an as yet unwritten C-coded list
> popend? Is this, or anything like it delivered with the standard
> configuration?
Not everything in Python is designed for speed. If you want a fast
stack class, you want a C-based stack class. This might've been a
specific example for C-extensions in one of the books. It was either
that or binary trees.
[snip]
> Leaving this aside, would you favor deleting append() since it is a
> stack-like LIFO operation rather than a randon-access operation? I am
> only proposing to add its inverse. The confusion, if any, comes from
> the presence of append withoug its inverse, and not the proposed
> addition of the the latter.
No, you're not just proposing the addition of a method. You're
proposing that lists also be stacks. There's a difference.
[snip]
> The current situation violates the design principle of pairing a
> function and its inverse (when it exists and is separate). Thus, Python
> has +/-, *//, exp/log, sin/asin (etc), frexp/ldexp, open/close, =/del
> (bind/unbind), tuple()/list(), upper/lower, split/join, atoX/str,
> but append/{missing}. I consider this principle important and this
> violation thereof bothersome.
append() is a special case of insert(). The inverse of insert() is
the del function. The specific inverse of append() is del list[-1].
Yes, not as convenient, but it's there.
> ====================================================================
>
> SUMMARY:
[snip]
> Finally, I believe that the addition of popend() to be as justifiable as
> that of list(tuple) (1.4) and dict.get() (1.5). All three are
> unnecessary but convenient. I expect popend() would be used more often
> than list(), though possibly less than get(). I expect that it would do
> more than either in making Python as-delivered more attractive to
> prospective newcomers.
list() isn't in the 1.4 library reference, so I'll just go by usage.
list() appears to be a conversion function, converting a tuple into a
list. This is a highly desirable function. There are many instances
when you want to use a tuple and not a list to store data, or even
when a tuple an not a list is returned. However, many functions
require a list and won't accept a tuple. The only way that I know of,
off-hand, to convert a tuple to a list is to loop over it and
construct the list by hand.
I'm not sure what dict.get() does, but I'm guessing it returns a tuple
of a key-value pair.
In either case, these don't change the functionality of the objects.
They simply simplify a common, and in the case of list() needed,
procedure.
To be honest, it sounds more like you don't want to create a stack
class. If you want a fast stack class, create a C-type.
Guido van Rossum
I have often thought about adding primitives to the list data
structure to make it usable as a stack as well as a queue. The set of
operations currently reflects the implementation more than anything
else:
- item = list[i] is very fast since it uses index arithmetic
- del list[i] is slower if it deletes closer to the front
- list.append(item) is very fast since it adds to the end
- list.insert(i, item) is slower but more general
To implement a stack, one would need to add a list.pop() primitive
(and no, I'm not against this particular one on the basis of any
principle). list.push() could be added for symmetry with list.pop()
but I'm not a big fan of multiple names for the same operation --
sooner or later you're going to read code that uses the other one, so
you need to learn both, which is more cognitive load.
To implement a queue, one needs similar operations that operate on the
front of the list, e.g.
def popfront(list):
item = list[0]
del list[0]
return item
def pushfront(list, item):
list.insert(0, item)
While an empty method is useful, I presume it generally is combined
with a 'not' operator, as in
while not stack.empty():
process(stack.pop())
That is actually done more efficiently (but less readable?) as
while len(stack):
process(stack.pop())
My current inclination is to leave the list data type alone and
implement a stack as a class that uses a list for its representation.
BTW the list will likely beat the "pure" tuple-based stack
implementation because it is much more memory efficient. The tuple
based implementation allocates and frees a tuple of length per
push-pop pair, and that's 24 bytes, assuming malloc overhead is 4
bytes. The list based implementation uses realloc but there's some
internal slack so the list only gets realloc'ed every 10 items (every
100 items if it's huge); and it only costs 4 bytes per item. (Double
the byte counts for 64-bit machines.)
--Guido van Rossum (home page: http://www.python.org/~guido/)
Hannu Krosing
Guido van Rossum wrote:
> While an empty method is useful, I presume it generally is combined
> with a 'not' operator, as in
>
> while not stack.empty():
> process(stack.pop())
>
> That is actually done more efficiently (but less readable?) as
>
> while len(stack):
> process(stack.pop())
Is'nt it faster and even more unreadable(assuming list for stack), to do
just
while stack:
process(stack.pop())
Hannu
Mike Meyer
In <34789c7a....@news.zip.com.au>, ska...@zip.com.au (John (Max) Skaller) wrote:
> The rule would be not to return information
> which was invariant -- the same before
> and after the change.
>
> Comments?
Well, as an old LISP hacker, I *like* operations that return a
reference to the changes/changed object.
For instance, sorting a list creates a change, and I expected it to
return a reference to self, so I naturally wrote:
l.sort().reverse()
Didn't work :-(. But writing two statements is only slighly more work.
Like I said, I kinda like the idea of a pop-like method to complement
append. On the other hand, I think going to the Perl extreme of having
push & pop at both ends, with multiple names for different data
structures, is definitely overkill, so maybe this isn't such a good
road to travel.
Along the same lines, the reason that len() is a function not a method
is because immutable types don't have methods. Which leads to the
question of why index() is a method, not a function?
Has no one but me ever wanted to find an object in a tuple? Though my
if 1.5 lets me apply a function to a list, the need will go away.
Barry A. Warsaw
>>>>> "TR" == Terry Reedy <tjr...@udel.edu> writes:
TR> Finally, I believe that the addition of popend() to be as
TR> justifiable as that of list(tuple) (1.4) and dict.get() (1.5).
TR> All three are unnecessary but convenient.
Actually, dict.get() is not just a convenience. It serves the useful
purpose of not raising an exception when the item is not present.
Rather than argue about the utility of list.popend(), I went ahead and
implemented it. On one hand I can see where it might be useful, and
the symmetry argument wins for me. I have one interface question:
what happens when you call popend() on an empty list? Perhaps you
raise an IndexError? On the otherhand, since I like the dict.get()
interface, I've implemented list.popend() to take an optional
argument, which is the object to return if the list is empty. If not
provided, None is returned.
Here's a patch against 1.5's Objects/listobject.c. Beware, it's only
been very minimally tested. I'm also not 100% sold on the name of the
method...
-Barry
Index: listobject.c
===================================================================
RCS file: /projects/cvsroot/python/dist/src/Objects/listobject.c,v
retrieving revision 2.44
diff -C2 -r2.44 listobject.c
*** listobject.c 1997/08/25 18:36:23 2.44
--- listobject.c 1997/11/24 18:39:37
***************
*** 555,558 ****
--- 555,580 ----
}
+
+ static PyObject *
+ listpopend(self, args)
+ PyListObject *self;
+ PyObject *args;
+ {
+ PyObject *retval = Py_None;
+
+ if (!PyArg_ParseTuple(args, "|O", &retval))
+ return NULL;
+
+ if (self->ob_size > 0) {
+ retval = PyList_GET_ITEM(self, self->ob_size-1);
+ if (list_ass_slice(self, self->ob_size-1, self->ob_size,
+ (PyObject*)NULL) != 0)
+ return NULL;
+ }
+ Py_INCREF(retval);
+ return retval;
+ }
+
+
#define NEWSORT
***************
*** 1022,1025 ****
--- 1044,1048 ----
{"reverse", (PyCFunction)listreverse},
{"sort", (PyCFunction)listsort, 0},
+ {"popend", (PyCFunction)listpopend, 1},
{NULL, NULL} /* sentinel */
};
Barry A. Warsaw
>>>>> "MM" == Mike Meyer <bounc...@contessa.phone.net> writes:
MM> Has no one but me ever wanted to find an object in a tuple?
MM> Though my if 1.5 lets me apply a function to a list, the need
MM> will go away.
Currently, the second argument to apply() must still be a tuple.
-Barry
David Ascher
> Rather than argue about the utility of list.popend(), I went ahead and
> implemented it.
Before this gets cast in jello, can I raise an objection to the name
'popend', which looked to me at first like a daemonic varation of the Unix
popen() call?
--david
Barry A. Warsaw
>>>>> "DA" == David Ascher <d...@skivs.ski.org> writes:
DA> Before this gets cast in jello, can I raise an objection to
DA> the name 'popend', which looked to me at first like a daemonic
DA> varation of the Unix popen() call?
I guess you didn't see my last paragraph! :-)
Guido van Rossum
I just found some Icon documentation for using Icon's lists as queues
(http://www.nmt.edu/tcc/help/lang/icon/queuelist.html). Icon's lists
have operations to push and pop at either end:
push --> +--------+--------+-------+--------+ <-- put
| L[1] | L[2] | ... | L[*L] |
pop <-- +--------+--------+-------+--------+ --> pull
I seem to recall that it also had "get" as an alias for one of these,
but I don't see it here, so it's anybody's guess whether get() means
pull() or pop().
I stil think that all this is best left out of the list object
implementation -- if you need a stack, or a queue, with particular
semantics, write a little class that uses a lists. That way you can
define your operations to make sense in your context.
class Base:
def __init__(self): self.L = []
def empty(self): return not self.L
class Stack(Base):
def push(self, item): self.L.append(item)
def pop(self): item = self.L[-1]; del L[-1]; return item
class Queue(Base):
def put(self, item): self.L.append(item)
def get(self): item = self.L[0]; del L[0]; return item
class Deque(Base):
def puthead(self, item): self.L.insert(0, item)
def gethead(self): item = self.L[0]; del L[0]; return item
def puttail(self, item): self.L.append(item)
def gettail(self): item = self.L[-1]; del L[-1]; return item
John Mitchell
On Mon, 24 Nov 1997, David Ascher wrote:
> > Rather than argue about the utility of list.popend(), I went ahead and
> > implemented it.
>
> Before this gets cast in jello, can I raise an objection to the name
> 'popend', which looked to me at first like a daemonic varation of the Unix
> popen() call?
>
> --david
I also thought it was Unix-related, pipe-open-daemon or something. "Pop
end", you say? Hmm: How about pop_end() (ie: like has_key) or
"poptail()" or "trimtail()". No tail jokes please. Okay, maybe a few.
- j
Alex Williams
In article <61ra86m...@cnri.reston.va.us>,
Barry A. Warsaw <bwa...@cnri.reston.va.us> wrote:
>the symmetry argument wins for me. I have one interface question:
>what happens when you call popend() on an empty list? Perhaps you
>raise an IndexError? On the otherhand, since I like the dict.get()
>interface, I've implemented list.popend() to take an optional
>argument, which is the object to return if the list is empty. If not
>provided, None is returned.
Ideally, I suppose, .popend() should raise an IndexError if called on
[] (just as taking a slice from the non-extant end does), but
optionally take a second argument which, if present, is the value
returned. A bit more complicated, but it gives one the ability to
both catch things as exceptions when the list may very well contain
any conceivable value, and the alternative.
--
--
[ Alexander Williams {tha...@alf.dec.com/zan...@photobooks.com} ]
[ Alexandrvs Vrai, Prefect 8,000,000th Experimental Strike Legion ]
[ BELLATORES INQVIETI --- Restless Warriors ]
Terry Reedy
FURTHER REPONSE TO COMMENTS (received as of Monday, and snipped)
Michael W. Ryan:
> So's a string. {a list}
So? I do not see this as relevant to my proposal. A string is a
list/sequence of chars, rather than of general PyObjects. A PyString is
not mutable while lists are. The relationship between strings and lists
is different than the relationship between stacks and lists.
> ... I think by making lists explicitely a stack as well as a list,
> you're blurring the distinction.
From my viewpoint, the distinction is less than and different from that
seen by you and others. See response below.
> ... To give a non-computer analogy: model cars (the plastic
> kind that sit on your shelf for display) don't have working engines
> because they're not supposed to be working cars, just visual
> representations.
I do not see how this refutes my proposal, which is to add one (repeat
*one*) more button to the control panel for Python's powerful list
engine so it will be easier to drive in certain situations. I care
nothing about non-working models, either of cars or of computers.
> The append() method is simply a commonly-used special case of
insert().
Yes. Similarly, the popend() method, by whatever name, is simply a
commonly-used special case of retrieve and delete. My point exactly.
=====================================================================
mryan:
> If you want a fast stack class, you want a C-based stack class.
I basically agree, except that we already have a
built-in-to-all-implementations-without-extension-and-recompilation
C-based list type which already does what is needed and which, in my
opinion, needs just one more interface function/method.
> No, you're not just proposing the addition of a method. You're
> proposing that lists also be stacks.
No! I am not proposing to change reality other than to add one (repeat
*one*) method. Nor do I insist that others change either their views of
reality or their coding practice, as long as they will accomodate me and
others who agree with me on this particular issue.
I am observing and noting, among other things
1) that stacks are a subset of lists;
2) that any list with decent access can be used as a stack;
3) that Python lists are well suited for use as stacks because their
implementation makes pushing and popping efficient;
4) that some Pythoneers, including me, have, do, and will use PyLists
as stacks in the sense that we have, do, and will continue to push
and pop objects to/from the end of lists with append() and whatever
version of pop we either write or have made available to us;
5) that this usage will be somewhat easier, faster, and more obvious
with the addition of a pop method.
{In response to my claim that popend is the inverse of append, in
analogy to several other such pairs in Python (as one justification for
adding it):}
> append() is a special case of insert(). The inverse of insert() is
> the del function. The specific inverse of append() is del list[-1].
We can argue this either way. My mental model is the following:
x = log(exp(x)) = sin(asin(x)) = pop(push(x))
As a technical matter, the last would not work with the implementation
of pop that I would advocate (but it could be made to do so by adding a
useless default None param).
> list() ...is a highly desirable {conversion} function. [snip]
I agree. Before list() was added, people had to either know, remember,
and use the peculiar Python idiom 'L=map(None,tuple)' or else write an
explicit list construction loop as you described. 'L=list(tuple)' adds
no new capability, only a little speed, and saves exactly 4 keystrokes.
It does make the pre-existing capability more easily known and used.
Ditto for my proposal.
The new (1.5) method, 'v=dict.get(k)', as I understand it, (and do check
the 1.5 additions doc before you try it) is a synonym for
try: v=dict[k]
except: v=None
Though unnecessary, the new method saves people the bother of either
writing out the previously and commonly used idiom or writing their own
function to encapsulate it. Ditto for my proposal.
> In either case, these don't change the functionality of the objects.
> They simply simplify a common ... procedure.
Ditto for my proposal.
> To be honest, it sounds more like you don't want to create a stack
> class.
No, and I never said I did. I only propose to add a method to the list
type, just as we are now adding a method to the dictionary type.
> If you want a fast stack class, create a C-type.
Why? We already have the list C-type.
====================================================================
?, as quoted anonymously (by David Ascher, from a post I have not
receive yet)
> Rather than argue about the utility of list.popend(),
> I went ahead and implemented it.
Thank you. I hope Guido likes your code and will add it.
=================================================================
David Ascher:
> Before this gets cast in jello, can I raise an objection to the name
> 'popend', {certainly - TJR} which looked to me at first like a
> daemonic varation of the Unix popen() call?
John Mitchell:
> I also thought it was Unix-related, pipe-open-daemon or something.
> Popend", you say? Hmm: How about pop_end() (ie: like has_key)
> or "poptail()" or "trimtail()".
I am more concerned with getting the method added than what we name it
(which does not need to be decided unless we do add it). I would accept
most any reasonable proposal. Here are my current thoughts.
'popend': I am neither attached to or completely happy with this,
especially after your comments. I partly used this instead of pop to
emphasize the pairing with append. But it can be (wrongfully) parsed
either as pope_nd [sic] or, as you note, p_opend [sic], neither of which
is good.
'pop_end': some people consider the '_' in has_key a mistake, but it
does help the mental parsing.
'pop': I didn't propose this partly to avoid even appearing to propose
'push' as a synonym for 'append'. And I wouldn't mind keeping push and
pop for bound usage, as described below.
'depend': Parse this as de_pend, as in undo ap_pend. This was my
original thought, but I switched to popend as being clearer.
After your comments on the latter, I see depend more favorably.
Any other suggestions?
=================================================================
Guido van Rossum:
> I have often thought about adding primitives to the list data
> structure to make it usable as a stack as well as a queue. The set of
> operations currently reflects the implementation more than anything
> else:... To implement a stack, one would need to add a list.pop()
> primitive (and no, I'm not against this particular one on the basis of
> any principle).
I am obviously glad to read this and hope, after further consideration,
that you will do so.
> list.push() could be added for symmetry with list.pop()
> but I'm not a big fan of multiple names for the same operation --
Neither am I, and I intentionally avoided suggesting this. Also see
comment below on binding the methods.
> To implement a queue, one needs similar operations that operate on the
> front of the list, ... popfront(list) ...pushfront(list, item)
1) I am not suggesting adding these and would like separate proposals
evaluated separately, each on their own merits.
2) For a queue, rather than a deque, only popfront (with append) is
necessary. On the other hand, the inverse pairing principle I have
expounded would commend adding both or neither.
3) Because of how PyLists are implemented, adding to and deleting from
the front are slower than at the end. To avoid copying on each
insertion/deletion, queues (and deques) might better be implemented as
classes with an internal pointer to a logical front different from the
front of the underlying list. Or a queue might use two lists, one
for pushing and the other for popping, with roles reversed when the
latter empties. Popfront would either keep an index into the
de-queue list or reverse it and pop the end!
> While an empty method is useful, I presume it generally is combined
> with a 'not' operator, as in
> while not stack.empty(): process(stack.pop())
> That is actually done more efficiently (but less readable?) as
> while len(stack): process(stack.pop())
Even more efficient is 'while stack: process...' or 'if stack: do..',
made possible by Python's clever assignment of boolean values to
composite structures. Not only have I NOT proposed an empty method; I
would oppose it (especially as a list method) as unnecessary,
inefficient, and contrary to the Python idiom. For a queue class, I
would prefer _nonzero__ to empty. Perhaps you can see now how
tantalizingly close PyLists already are to being directly used as
stacks.
> My current inclination is to leave the list data type alone and
> implement a stack as a class that uses a list for its representation.
Why take the time hit? Here are a two more reasons that I consider
stacks a special case (relative to queues and deques):
1) To my knowledge, stacks are much more common than queues, deques, and
other structures. Parsing is one application. Speeding up recursive
functions with loops and explicit stacks is another.
2) If a section of an application needs just one stack, one can already
write (and I learned this from respected Python gurus):
stack = []
push = stack.append
It would be very nice, (and especially easier for beginners) to be able
to write the analogous
pop = stack.whatever
instead of the less efficient special case function
def pop(): global stack; tem = stack[-1]; del stack[-1]; return tem
If the stack is a local variable within a function, as would be the case
for a recursion conversion, then a nested form is needed:
def pop(s=stack): tem = s[-1]; del s[-1]; return tem
With push and pop thus defined, one can simply write
push(v); w = pop(), etc.
{second response}
> I stil think that all this {stack,queue,&deque methods}
> is best left out of the list object implementation
Why should we have append but not pop/popend/depend? It would be so
easy to add, and arguably useful. The others are separate issues.
{Base,Stack,Queue,Deque class code deleted}
I would like to see a datastructure library module that collected
together these and others, but that is a separate issue.
Terry J. Reedy
Christian Egli
For a while I was afraid this popend thing would get out of hand, but
alas the almighty night came on the scene and spoke thus:
Guido> I still think that all this is best left out of the list
Guido> object implementation -- if you need a stack, or a queue,
Guido> with particular semantics, write a little class that uses a
Guido> lists. That way you can define your operations to make sense
Guido> in your context.
Guido, thanks for keeping this language simple and clean.
--
Christian Egli
Switching Test Solutions AG, Friesenbergstr. 75, CH-8055 Zuerich
Michael W. Ryan
tjr...@udel.edu (Terry Reedy) writes:
> FURTHER REPONSE TO COMMENTS (received as of Monday, and snipped)
>
> Michael W. Ryan:
> > ... I think by making lists explicitely a stack as well as a list,
> > you're blurring the distinction.
>
> From my viewpoint, the distinction is less than and different from that
> seen by you and others. See response below.
A list and a stack are different concepts. Just because they're
similar internally is conincidence and doesn't mean they should be the
same object.
> > ... To give a non-computer analogy: model cars (the plastic
> > kind that sit on your shelf for display) don't have working engines
> > because they're not supposed to be working cars, just visual
> > representations.
>
> I do not see how this refutes my proposal, which is to add one (repeat
> *one*) more button to the control panel for Python's powerful list
> engine so it will be easier to drive in certain situations. I care
> nothing about non-working models, either of cars or of computers.
Classes are models. You said yourself that there are three ways to
implement a stack, internally. Which one you choose depends on what
characteristics you need to model. OO design is modelling. By making
lists function as BOTH lists and stacks you're doing the following:
1) Forcing an implementation of stacks,
2) Causing potential confusion in casual programmers,
3) Blurring the distinction between the concept of a list and a
stack.
Your argument is based solely on the conincidence that lists are
implemented in a similar manner to a list. This does NOT mean that
they are the same concept. Nor does it mean that they should be the
same objects. A better proposal would be to implement a builtin stack
object.
> > No, you're not just proposing the addition of a method. You're
> > proposing that lists also be stacks.
>
> No! I am not proposing to change reality other than to add one (repeat
> *one*) method. Nor do I insist that others change either their views of
> reality or their coding practice, as long as they will accomodate me and
> others who agree with me on this particular issue.
Yes, you are.
> I am observing and noting, among other things
> 1) that stacks are a subset of lists;
So are strings and tuples.
> 2) that any list with decent access can be used as a stack;
That's coincidence.
> 3) that Python lists are well suited for use as stacks because their
> implementation makes pushing and popping efficient;
I'm not arguing efficiency. I'm arguing language clarity. There's a
difference here.
> 4) that some Pythoneers, including me, have, do, and will use PyLists
> as stacks in the sense that we have, do, and will continue to push
> and pop objects to/from the end of lists with append() and whatever
> version of pop we either write or have made available to us;
Then, as I said, suggest a builtin stack type. Or, if not, I'm sure
if it's that useful, it won't be hard to make it a C-type that's part
of the standard library.
> 5) that this usage will be somewhat easier, faster, and more obvious
> with the addition of a pop method.
More obvious? How? Is it a list or a stack? Just because something
is faster and easier, doesn't mean that it's a good thing.
> > If you want a fast stack class, create a C-type.
>
> Why? We already have the list C-type.
Because lists are NOT stacks.
Joel Neely
Michael W. Ryan wrote:
>
> tjr...@udel.edu (Terry Reedy) writes:
>
> > FURTHER REPONSE TO COMMENTS (received as of Monday, and snipped)
> >
> > Michael W. Ryan:
> > > you're blurring the distinction.
> >
> > From my viewpoint, the distinction is less than and different from that
> > seen by you and others. See response below.
>
> similar internally is conincidence and doesn't mean they should be the
> same object.
>
<life-imitates-art>
Saturday Night Live had a famous mock commercial that contained
something like the following:
Family member 1: Sparkle! It's a floor wax!
Family member 2: Sparkle! It's a dessert topping!
Announcer: You're both right!
</life-imitates-art>
<opinion>
A list is a SEQUENTIAL data structure, with no allowance for random
access. To traverse a list, one must start at the/an end and obtain
from each element a reference the next element in the chosen direction.
I said "the/an end" and "chosen direction" because singly-linked lists
can be entered at only one end and traversed in only one direction,
while doubly-linked lists can be entered at either end and traversed in
both directions. Unlike arrays, one cannot jump to an arbitrary
element in the middle. Unlike many other linked or recursively defined
data structures, a list is inherently one-dimensional, with no forks
in the road.
When use pen and paper to make a list, I feel that I have a perfect
right to add or cross off elements from either end, without being
accused of destroying the "list-ness" of my list. (If I'm VERY
careful with my penmanship, I may even be able to insert or delete
elements in the middle, but that still doesn't change my point here.)
I also feel that it is perfectly legitimate for me to notice whether
my pen-and-paper list is empty (including the possibility that it
once contained some stuff, all of which has been crossed off).
A stack is an ABSTRACT data structure, with the constraints that one
must be able to add and delete elements at one "end" only, and that
one must be able to determine whether the stack is empty.
I can implement such a concept by using a pen-and-paper list with all
insertions/deletions at the end of my choice (such choice being
invariant
for any specific case!), by a linked data structure with insertions/
deletions at the "head" end, by an array with a pointer/counter, etc...
"Asset" and "mode of transportation" are different concepts, but my
autmobile fulfills both roles quite nicely, thank you.
</opinion>
-jn-
--
-----------------------------------------------------------------------
public class JoelNeely extends FedEx { // (
String workEMail = "joel....@fedex.com"; // )
String workPhone = "901-375-6586"; // (
boolean speaksForCompany = false; } // C[_]
Guido van Rossum
> From: Joel Neely <joel....@fedex.com>
> <opinion>
>
> A list is a SEQUENTIAL data structure, with no allowance for random
Not a Python list. In Python (and many other languages, including
Perl, and Python's predecessor ABC), "list" is the word used for a
flexible array. For such lists, indexed access times are O(1).
Magnus Lycka
M.-A. Lemburg wrote:
> [Can't remember who actually had this tuple idea... it
> wasn't me, that's for sure :]
It's mentioned in Programming Python chapter 13.
I threw together a little module with list and tuple based
stacks with just push, pop and empty methods.
# Stack module
class lstack:
def __init__(self): self.stack=[]
def push(self,x): self.stack.append(x)
def pop(self): x=self.stack[-1]; del self.stack[-1]; return x
def empty(self): return not self.stack
class tstack:
def __init__(self): self.stack=None
def push(self,x): self.stack = x, self.stack
def pop(self): x, self.stack = self.stack; return x
def empty(self): return not self.stack
import time
def pushloop(stack, n):
for i in xrange(n): stack.push(i)
def poploop(stack,n):
while not stack.empty(): stack.pop()
def bench(stack,n):
start = time.clock()
pushloop(stack,n)
middle = time.clock()
poploop(stack,n)
stop = time.clock()
print "Push",n,"takes",middle-start,"seconds"
print "Push",n,"takes",stop-middle,"seconds"
print "In all",stop-start,"seconds"
return stop-start
from sys import argv
from string import atoi
n=atoi(argv[1])
l=lstack()
print "List based stack"
ltime = bench(l,n)
t=tstack()
print "Tuple based stack"
ttime = bench(t,n)
if ltime > ttime:
print "List stack takes",(ltime/ttime-1)*100,"percent longer."
else:
print "Tuple stack takes",(ttime/ltime-1)*100,"percent longer."
#end of file
With n=10000 the list based stack takes around 50% longer on my
computer (Python 1.4 in DOS-box under Win95). With n=100000 the
difference is around 20%, but it varies considerably from time
to time. N=100000 takes roughly 20 seconds on a Pentium 100MHz,
so the operations take about 0.1ms each. (With push replaced with
pass, it takes 0.6 s, so loop overhead is not huge.)
Mark's analysis of this was a bit more thorough, and his classes were
also more elaborate, including get_item, length etc. When random
access to the stacks are also desired, lists are faster, but for
these pure LIFO stacks it seems tuples are a bit quicker.
Magnus
--
Magnus Lycka, S/W Engineer, M.Sc.E.E; Folktrov. 6C, 907 51 Umea, Sweden
Tel: +46(0)90 198 498, GSM: +46(0)70 582 80 65, Fax: +46(0)70 612 80 65
<mailto:magnus...@tripnet.se> <http://www1.tripnet.se/~mly/>
Guido van Rossum
> > [Can't remember who actually had this tuple idea... it
> > wasn't me, that's for sure :]
>
> It's mentioned in Programming Python chapter 13.
>
> I threw together a little module with list and tuple based
> stacks with just push, pop and empty methods.
[interesting analysis deleted]
Beware though: when you have popped 10,000 items on the tuple stack
and then delete it (instead of popping the items one by one) the
interpreter may run into a stack overflow, because the tuple_dealloc()
function calls itself recursively 10,000 levels deep... No fun on a
PC!