Deque.append() should return popped item

Ideas
1

If a deque is used with a fixed size, appending to one end will pop from the other end. However, there’s currently no way to reference this popped item. If I want to use it as a FIFO, I need to make sure that I pop from the right direction first, e.g.:

d = deque([],maxlen=1)

d.append(1)
old_value = d.popleft()
d.append(2)

This can be error prone if I accidentally pop from the wrong direction (though obviously not relevant in the n=1 scenario)

IMO this would be nicer if I could just do

d = deque([],maxlen=1)

d.append(1)
>> None
d.append(2)
>> 1

This would likely also imply

d = deque([],maxlen=3)
d.extend([1,2,3])
>> ()
d.extend([4,5,6])
>> (1,2,3)

Which seems fine to me? May even be useful to know the number of items popped during an operation, if queue length is unknown or something.

I considered making a PEP, but the guidelines said to socialize the idea first in this ideas forum, so I figured that might be a good idea :blush:

Thoughts? Anyone see a reason why this might be a bad idea to do?

Edit:

For additional context, the issue I’m facing is as follows:

I have a physical system where objects are traversing through. If an object is there, it needs to traverse through a number of steps, if it’s not there, we can skip a lot of stuff.

At every timepoint, we push in a new Widget, and pop out an old one. The machine start out being empty.

One part of the code would look something like this

queue = deque([], maxlen=5)
...
widget_entered = input_controller.widget_entered()
obj = Widget() if widget_entered else None
try:
  old_obj = queue.popleft()
except IndexError:
  pass
queue.append(obj)
if old_obj:
  output_controller.process(old_obj)

Which could be rewritten to

queue = deque([], maxlen=5)
...
widget_entered = input_controller.widget_entered()
obj = Widget() if widget_entered else None
if old_obj:= queue.append(obj):
  output_controller.process(old_obj)
1 Like
2

People’s code would be easier to understand, if they just first checked its length against maxlen and if needs be grab the value of deque[0] before appending, instead of grabbing the return value from deque.append, and testing if it’s None or not.

But I like the idea of there being a deque like class that does this on .append, possibly a third party one.

3

That wouldn’t allow you distinguish None, (unless you check the length first):

d = deque([],maxlen=1)
d.append(None)
>> None # nothing popped
d.append(2)
>> None # popped item

But for extend, it does work.

1 Like
4

It could also return the empty set, if distinguishing between None and nothing is important, so the return would be the same as my suggestion for extend. However you could argue that if that’s important, one could just use extend with a single object.

d = deque([],maxlen=1)

d.append(1)
>> ()
d.append(2)
>> (1)

From my point of view, I would prefer it just returning None, as or my use case it’s not important wether anything was popped or not, what’s important is wether anything “fell out of the queue” that I need to act on.

5

That doesn’t work for the empty tuple. I’m assuming you meant return a tuple of 1 item: (popped_item,)?

6

Yeah, that’s what I meant :blush:

7

That’s an error whether your deque has a fixed size or not.

For a fixed-size deque, I think it’s intentional to distinguish between items you expicitly remove from a deque and items that “fall off” because a new item is added to a full deque. Use a fixed-size deque when you don’t care about older items being pushed off. If you want everything that’s ever been added to the deque, don’t use a fixed-size deque.

Further, it may be that whoever adds to the deque wouldn’t know what to do with values returned by append anyway, as they are only a “producer”, not a “consumer”.

8

Could you avoid editing messages to address a message posted afterwards?

1 Like
9

I think the deque as it stands is the best method of modelling a physical system that has a fixed number of slots for objects moving through it - which is exactly my use case. It’s basically a FIFO queue that you can iterate over.

In that scenario, I don’t want everything that’s been added to the deque - I want the popped item. I can pop it first, but that’s extra housekeeping for me. And in that scenario, I’m not even using the fact that a deque has been initialized with a max length, if I’m doing this anyways:

queue_length = 5
d = deque([],maxlen=queue_length)
...
obj = None
if len(d) == queue_length: # Could be == d.maxlen, but there's really no difference
  obj = d.popleft()
d.append(new_obj)

versus

obj = d.append(new_obj)

In other words, I don’t see a downside to just returning the popped item(s). I don’t see how it would adversely affect existing code. It can be completely ignored by existing code, with no obvious side effects. It would give me more information about what’s happening underneath, as there’ currently no way to see if an append currently pops out anything.

As I see it, there are scenarios where it wouldn’t matter, and scenario where some code can be simplified. And if that’s the case, I’d call it an improvement.

10

This seems like it would be straightforward to build yourself as a subclass of the stdlib deque class. That’s almost certainly a far better solution than trying to deal with the backward compatibility issues of changing the stdlib class.

11

I probably will just build it myself :smile: From more of a purity of computation point of view, it annoys me that my implementation would then do a length check, followed by a pop, and then call append which will do a length check and would have popped. But from an interface point of view, it would be the same as I’m suggesting here.

I took a quick look at the at the cpython implementation, and from what I could tell the implementation would look fairly straight forward. However I’ll definitely defer to you in that assessment. What kind of backwards compatibility issues do you foresee?

At first glance, I would think that changing a non-returning method to a returning method would not risk backwards compatibility, whereas the inverse obviously would.

12

Code that doesn’t expect the call to return a value. Documentation and training courses that would need to be changed. Tests that would need updating to deal with the changed method signature. Etc.

13

So pop it when you need it. Why are you fixing the length of the deque? The use-case for a fixed-length deque is basically a queue for items with an expiration “date”. When newer items come in, the older items are discarded to make room for them. From the documentation,

Bounded length deques provide functionality similar to the tail filter in Unix. They are also useful for tracking transactions and other pools of data where only the most recent activity is of interest.

I can’t tell if you are using the fixed-size deque as a memory-saving technique that forces you to deal with old items when new items come in? The idea of a method that both adds to one end and maybe returns a value from the other seems just a bit too specialized for the base deque class. This should probably be defined by a new class that uses a deque.

1 Like
14

As an aside, the insert method currently just raises an IndexError should you attempt to add an element to a full bounded deque, rather than decide from which end to eject a value.

Would you have insert make such a decision, or continue to raise an IndexError?

15

I think this is a very valid application of deque.

However, I don’t think modifying append/extend is an option here. They are conceptually in line with list.append/extend and mutable sequences in general.

And deviation from this pattern is unlikely to be seriously considered.

However, what might do the trick is introducing new method:

class new_deque(coll.deque):
    def popleft_append(self, item, sentinel=None):
        if (n := len(self)) == self.maxlen and n:
            rtrn = self.popleft()
        else:
            rtrn = sentinel
        self.append(item)
        return rtrn

But the issue is that there are many variations of this:

  1. What happens with this method when maxlen is None?
  2. Should it pop only when len(self) == maxlen or whenever len(q) > 0?
  3. Should it have such method for both ways or only one? If both, should it be a flag or a separate method?
  4. Should it have append only or extend version too?

Although the application is valid, can you find some existing code examples where this would have been useful if existed?

If this becomes too complex in providing flexibility for all the cases above, is it worth implementing it? Or would it be better to let user use appropriate combination of methods according to necessity?

I would suggest coming up with specific concept first. Implementation is short and quick, so if you want to propose something along these lines I think presenting Python version you have in mind would be best.

16

Would you have insert make such a decision, or continue to raise an IndexError?

I would not change insert at all. I would only change the methods that already make that decision, and already pop something out behind the scenes.

I need it when it’s being pushed out of the deque. It’s only being pushed out when a new thing is added. My use case is basically a processing pipeline, where objects enter in their rawest format in the beginning, and each step corresponds to a physical interaction with an object in that position. When it’s popped out in the end, it’s fully processed. Yes, I can pop it first, and then append, but popping and appending is the same thing in my scenario - and in the underlying C implementation. Which I why I figured that just surfacing the existing implementation would make sense.

17

That makes sense and is a very valid argument.

I’m glad I didn’t go straight to writing a PEP then :smile:

If introducing a new method, I think I’d rather do it in CPython. From what I can tell the simplest implementation is just changing this line from Py_DECREF(olditem); to return olditem. The Py_DECREF would then happen once the object is no longer referenced in python (if my python runtime understanding is correct, which it very well may not be!).

I would do it for both directions - conceptually it’s the same, appending something to a deque with a max length is an implicit pop with no option of catching the popped object.

Again, I would do it for both, with the difference that append would return None or the popped item, whereas extend would return an empty tuple or a tuple of the popped objects.

Thanks. I think I’ll take a look around to see if I can find cases of deque being used with maxlength, where things are being appended and popped.