mutating a deque whilst iterating over it

[Avi Gross]

I agree both with the idea that it is not good to mutate things during
iteration and that some things we want to do may seemingly require
effectively something like a mutation.

I want to consider what data structure might capture a normal activity like
having a to-do-list for TODAY and another for further in the future. I might
sit down in the morning and look at my day and the list of activities I was
going to do. I might note new activities to add, some that are done or moot
and can be removed and some that should be done earlier or deferred to later
or even into the next day. This does not seem easy to do iteratively.
Weirder, if I throw each item at the end, I end up with the same items in
the same order.

So creating a data structure (such as an object like a deque but with more
specific functionality) might take some work. To begin, you might want an
iteration protocol that locks it till done. Not necessarily because of
mutation, though. Within the iteration you might have code asking for what I
might consider delayed actions. You can ask for the current item to be
deleted or moved to a data structure for the next day and it will not be
done now but some reference might be stored inside the object such as a
DELETE list and a MOVE list. You may also have lists with names like HIGH,
MEDIUM and LOW or priorities from 1 to N. I don't mean python lists, just
some kind of way of assigning some meaning to each item as you go. You may
even want a way to break a task into multiple parts or declare a dependency
between them such as one having to be done before the other.

When you are done iterating, presumably the data structure will then reorder
itself in a scenario where mutability is done harmlessly and a new list or
deque or whatever is reconstituted and you can unlock.

I do note that years ago I took a course in time management that ended up
spending way too much time doing this kind of task on paper multiple time a
day with lots of erasing or rewriting. The idea was to get more of the
important things done. These days, I am so interrupt-driven that such a
system is not useful albeit a nice automated way might be helpful as my day
constantly mutates to become unrecognizable.

There are project management tools along the lines I describe that try to
manage timelines and dependencies across multiple groups and measure
deliverables and note when something will cause delays in others and so on.
Obviously, beyond the scope but my point is they do not necessarily operate
in one pass over the list and are quite a bit more complex.

-----Original Message-----
From: Python-list <python-list-bounces+avigross=verizon.net at python.org> On
Behalf Of Dan Stromberg
Sent: Saturday, February 13, 2021 2:13 PM
To: duncan smith <duncan at invalid.invalid>
Cc: Python List <python-list at python.org>
Subject: Re: mutating a deque whilst iterating over it

On Sat, Feb 13, 2021 at 10:25 AM duncan smith <duncan at invalid.invalid>
wrote:

> On 12/02/2021 03:04, Terry Reedy wrote:
> > On 2/11/2021 3:22 PM, duncan smith wrote:
> >
> >>        It seems that I can mutate a deque while iterating over it 
> >> if I assign to an index, but not if I append to it. Is this the 
> >> intended behaviour?
>
> What I was really wondering was whether the behaviour is as it is 
> because of the implementation or because it's how deques should 
> ideally behave. i.e. In my implementation do I stick strictly to the 
> same API, or allow it to differ? In some places I'm jumping through 
> hoops to stick to the API, and (when it comes to iteration) I'm 
> jumping through different hoops for different types of container (e.g. 
> lists versus deques). BTW, the reason I am implementing these at all 
> is that my containers are on-disk. Cheers.
>
> collections.deque appears to take the approach of  "allow everything 
> we
can based on our implementation, and trust the client not to overuse
features".

In fact, in Python, "over abstraction" is often seen as a bad thing, mostly
because it slows things down so much.

If you want something more abstracted, you might have a look at:
https://stromberg.dnsalias.org/~strombrg/linked-list/
https://pypi.org/project/linked_list_mod/

(Both URL's are about the same module)

Note that linked_list_mod is quite a bit slower than a collections.deque.
Deques use a clever-but-hidden trick to gain a lot of speed - it's really a
linked list of built in lists, which gives better locality of reference that
masks CPU caches very happy.  linked_list_mod goes for abstraction and
simplicity.
--
https://mail.python.org/mailman/listinfo/python-list