Unless I'm missing something, the only way to tell if a deque is empty is
to try and pop() something and catch the resulting IndexError. This is
not only awkward, but mutates the data structure when you may not want to.

It should be trivial to implement, and run in O(1) time.

I just realized my request may have been ambiguous; empty() is a
predicate, not a verb. Doc should be something like:

"""Return true if the deque is empty. Return false otherwise."""

Sigh. It looks like you can do what I want after all, by just using the
deque object itself, i.e.:

q = deque()
while (q):
   ...

This should be changed to a docs bug -- the doc page for deque should
mention this, or include an example of this usage. It's logical that it
works this way, but not entirely obvious.

What would you suggest? The docs already say:

Though list objects support similar operations, they are optimized 

for fast fixed-length operations and incur O(n) memory movement costs
for pop(0) and insert(0, v) operations which change both the size and
position of the underlying data representation.

How would you suck elements out of a list? Probably with something
like:

    while mylist:
      elt = mylist.pop()

Aside from possible performance issues it's not clear that you would use
a deque object differently than a list in this context.

In retrospect, it's obvious that "while mydeque" is indeed the way to
process the queue, yet, when I was reading the docs, I didn't come away
with that.

The statement, "list objects support similar operations", is wishy-washy.
It is not the same as saying "deque is a subclass of list" (which isn't
true), nor "the set of operations supported by deque is a superset of
those supported by list" (which also isn't true). Thus, you're left
having to interpret the statement as a handwave that deques are sort-of
list-like things, with some (indeterminate) set of operations in common.
It's not at all obvious (or at least it wasn't to me) that one of those
operations is evaluating the container in a boolean context to test for
emptiness.

Anyway, to more concretely answer your question, I'd just make the plain
statement, "An empty deque evaluates as false", somewhere right on the
page where the methods are listed.

I changed this to a doc issue for 2.6/3.0 whenever.

I have two objections to adding "An empty deque evaluates as false".
First, it implies (falsely) that it could be otherwise; since deque has
no __bool__ method, its __len__ method is used, so that bool(d) ==
(len(d)!=0). Second, it misses better doc enhancements that might make
the statement I just made clearer and easier to find.

1. Ref manual Expressions Boolean Operations says
   "In the context of Boolean operations, and also when expressions are
   used by control flow statements, the following values are interpreted as
   false: False, None, numeric zero of all types, and empty strings and
   containers (including strings, tuples, lists, dictionaries, sets and
   frozensets)."

For 3.0, I suggest replacing "and empty strings..." with
"empty strings and sequences (including strings, bytes, bytearrays,
tuples, lists, and Userlists and deques from the collections module),
and other empty containers (sets, frozensets, dictionaries, and
Userdicts and defaultdicts from the collections module)."
Anything else I forgot? Adjust for 2.5/6.

The sentence after next "User-defined objects can customize their truth
value by providing a __bool__() method." should say '... __bool__ or
__len__ method.', with __len__ linked to object.__len__ just as __bool__
is linked to object.__bool__.

2. The LibRef entry for built-in function bool says simply "Convert a
   value to a Boolean, using the standard truth testing procedure".
   Extended that with " described in the Language reference in the __bool__
   and __len__ entries of the Special methods subsection and in the Boolean
   operations subsection."

I think you're missing the point. Imagine you are somebody who doesn't know
Python internals. You're looking at the doc page for deque and ask yourself
the question, "How do I tell if one of these is empty?". There's no
information ON THAT PAGE that answers that question. Your explanation is all
about "How do I compute the boolean value of a container?" The logical gap
is that you need to understand that to tell if it's empty, you should compute
the boolean value.

You give the page on boolean operations as part of the answer, but you need
to know to go look at that page in the first place. I should be able to look
at the page that describes a deque and find out everything I need to know
about that class on that page.

Essentially, what you're saying is that deque inherits some behaviors from
container, one of which being that if you convert a container to a bool, it
is True iff the container is not empty. So, there should be something on the
deque page which points to that information.

Explicit is better than implicit :-)

Sorry Roy, I think you're way off base on this one. There are standard
ways to test for an empty container "if c:" or "if len(c)" or "if len(c)

0". This is Python 101.

Closing this one as it has nothing to do specifically with
collections.deque() and is already covered in the Ref Manual.