On 1/1/21 12:14 PM, Jeff Allen wrote: > On 01/01/2021 14:50, Jonathan Fine wrote: >> ... >> To summarise, it's loops / cycles in the representation of the data >> that's the problem. ... . >> >> Final idea. Perhaps a tool to detect cycles in data might be a good idea. >> > Detecting cycles will involve a lot of bikeshedding. (Sorry, couldn't > resist.) > > But you're right, that's a better word for discussing the problem. > Steven's problem data structures are cyclic graphs. I don't agree that > such structures are a sign one is doing something wrong (outside the > naive approach to printing them out). > > If memory serves me right, what we're talking about is finding and > walking a "spanning tree" of the graph. There is a twist in our case > that we would like to insert a special object where a link was elided > to break the cycle: an object that maybe contains the original > reference but would reproduce as "..." in print. > > Since it appears necessary to create a data structure with as many > nodes as there are in the tree, just to remember where we've been, we > may as well say that the required result takes the form of an iterable > of the nodes, which may subsequently be iterated by a consumer. > Actually, I can think of two styles of iterator: one where "..." > objects are skipped by a "processing" iterator, and one where they are > delivered by a "print" iterator. It is valid to do this with objects > that can't be hashed, so the structure is perhaps a dict keyed by id. > > Would this be possible as a general capability? I think only if the > references were in the __dict__ of each instance. With a built-in, one > is at the mercy of the implementor. But we must have to do something > very similar to pickle arbitrary (potentially cyclic) structures, > which is likewise dependent on special help from the particular > built-in type. Can something be founded on |||__getstate__| ? > > Happy New Year > > Jeff Allen > I believe that one solution to detecting the cycles is to create a set of the object IDs you have visited and started to print. If you come across an ID you have already seen, this point is in a cycle. Sets are fairly compact and intentionally fast to search for an item.
-- Richard Damon _______________________________________________ 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/OXZ4GP27ZWDEONUZQ3MCBOHPQYAM2FZJ/ Code of Conduct: http://python.org/psf/codeofconduct/
