On 2021-01-01 at 16:34:15 +1100,
Steven D'Aprano <st...@pearwood.info> wrote:
> This isn't so much an idea for Python, as a request for ideas to solve a
> problem in Python.
[examples of recurive data snipped]
> The built-ins handle these cases okay. Likewise the copy.deepcopy
> function takes care to avoid getting stuck in a loop with recursive
> data structures.
The POSIX utilities tar and find (and I'm sure there are more) also deal
with this.
> On the other hand, when I write code to process nested data
> structures, I always worry about such recursive patterns, but actually
> doing something about it is too hard. So I just ignore the risk and
> feel guilty about it. I'm sure I'm not the only one who feels guilty
> about ignoring this problem.
Sorry about the guilt.
Know your requirements! Specify your constraints and limitations!
Document, document, document! But you know that stuff already.
> To say nothing of those who don't even know there's a problem to worry
> about.
*sigh*
> Is there something we can do to make it easier for people to deal with
> recursive data structures, like the list repr and deepcopy code does?
> Is there a pattern we can abstract out and provide as a tool or recipe
> for people to use in their own code?
My first thought was that all of those things (printing a list,
navigating a tree^H^H^H^H cyclic graph, deepcopying data, etc.) are the
recipes, and that every use case is different, but that's kind of a cop
out.
If I had to "abstract out" a pattern or an algorithm, it might look
something like this:
1. initialize been_there to an empty set
2. initialize go_here to a collection containing the root of the data
(e.g., go_here = [root])
3. if go_here is empty, then stop
4. remove one element from go_here, assign it to current_node
5. if current_node is in been_there, go back to step 3
6. deal with current_node
7. add current_node to been_there
8. add each of current_node's "next node"s to go_here
9. go back to step 3
IOW, keep track of where you've been, and don't go there again. I
probably should say out loud that go_here should contain the id of nodes
rather than references to nodes (to avoid having to know too much about
how to determine equality amongst nodes), but I was trying to stay away
from too many Python- or implementation- specific details.
Yes, it takes additional time and space not to dump core. No, you don't
have to do this if you're certain that your data isn't recursive (even
if your data structure is).
But that seems too obvious and (at least at this level) too simple.
It's almost right out of any graph (vertexes and edges) library that
handles non-acyclic graphs, directed or not. So maybe it doesn't
provide for a pretty "..." at the right place in the report. What am I
missing?
_______________________________________________
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/O62LCGZXLEW2N3X7QOGRS2U3EOIRGUV2/
Code of Conduct: http://python.org/psf/codeofconduct/
