[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On Fri, Jan 01, 2021 at 02:53:33PM -0500, Eric V. Smith wrote: > On 1/1/2021 2:00 PM, Jonathan Fine wrote: > > > >By the way, this surprised me. Would anyone like to explain this? > >    >>> id(f()), id(f()) > >    (139927013695536, 139927013695536) > > > id's are only unique while an object

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On Fri, Jan 01, 2021 at 11:42:12AM -0800, Brendan Barnwell wrote: > On 2020-12-31 21:34, Steven D'Aprano wrote: > >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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

It might not be that surprising to use a list if you are already using that list to keep track of your position in the hierarchy. You can probably assume that most of the time the depth is fairly low so the cost of scanning is low enough that the cost of building and updating the set costs enough

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

Interesting to look at the code for some of this. list.repr and dict.repr seem to be taking the "construct a set of seen items" approach. Except it's not using a set of ids, it's doing a linear pass over a list of visited PyObjects each time (which seems somewhat surprising to me, though it's

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 1/1/2021 2:00 PM, Jonathan Fine wrote: By the way, this surprised me. Would anyone like to explain this?     >>> id(f()), id(f())     (139927013695536, 139927013695536) id's are only unique while an object exists. Here the object returned by the first call is discarded after its id is

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 2/01/21 6:14 am, Jeff Allen wrote: 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. In general you need more than that, I think. If you're printing a representation of the graph, you want to know about

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 01/01/2021 19:36, Richard Damon wrote: On 1/1/21 2:00 PM, Jonathan Fine wrote: Hi Richard You wrote 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,

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 01Jan2021 16:34, Steven D'Aprano wrote: >This isn't so much an idea for Python, as a request for ideas to solve a >problem in Python. > >Back in the early days of Python, printing recursive lists could crash >the interpreter: > >a = [1, 2, 3] >a.append(a) >print(a) > >If you try

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 2020-12-31 21:34, Steven D'Aprano wrote: 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?

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 1/1/21 2:00 PM, Jonathan Fine wrote: > Hi Richard > > You wrote > > 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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

Hi Richard You wrote 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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 1/1/21 12:12 PM, Jonathan Fine wrote: > Hi Richard > > You suggested > > A very simple and in my mind reasonable use for this is to build a > representation of a graph, where each node is represented by a > list (or > some other collection), and the connections are denoted by

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

Hi Jeff > 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). > Thank you for agreeing with me,

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

A variant of the problem is the "occurs check", used in theorem proving: https://en.wikipedia.org/wiki/Occurs_check Removing the occurs check reduces the cost of unifying two terms (t1, t2) from *O(size(t1) + size(t2))* to *O(min(size(t1), size(t2)))*, which is why Prolog implementations don't do

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

Hi Richard You suggested A very simple and in my mind reasonable use for this is to build a > representation of a graph, where each node is represented by a list (or > some other collection), and the connections are denoted by adding to > that collection the nodes that are adjacent (or maybe a

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 1/1/21 9:50 AM, Jonathan Fine wrote: > Hi > > I'd say the problem isn't recursion. Here I'm using the definitions > given in: > https://en.wikipedia.org/wiki/Recursion > > https://www.cs.utah.edu/~germain/PPS/Topics/recursion.html >

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

Hi I'd say the problem isn't recursion. Here I'm using the definitions given in: https://en.wikipedia.org/wiki/Recursion https://www.cs.utah.edu/~germain/PPS/Topics/recursion.html Rather, it's that the data has a loop (or cycle) in it. A simple example of this is >>> x = [] >>>

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On Fri, Jan 1, 2021 at 2:21 PM Marco Sulla wrote: > On Fri, 1 Jan 2021 at 06:38, Steven D'Aprano wrote: > > Relevant: https://bugs.python.org/issue42801 > > Can't reproduce on the latest trunk (3.10). I get 1989 as a result. > There were a spate of bugs about this, and was fixed by

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On 2021-01-01 at 16:34:15 +1100, Steven D'Aprano 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

[Python-ideas] Re: Standard tool for iterating over recursive data structures?

On Fri, 1 Jan 2021 at 06:38, Steven D'Aprano wrote: > Relevant: https://bugs.python.org/issue42801 Can't reproduce on the latest trunk (3.10). I get 1989 as a result. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email