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
    fairly compact and intentionally fast to search for an item.


Indeed. But I see a flaw. The problem is that we want to know about
EQUALITY of nodes, not equality of the ID (memory address in disguise)
at which the node is stored. 

As to the first, just because to points have equal values doesn't mean
that we have recursion.

That is why I put the id()s in the set, the id()s are by definition
hashable, and an object always has the same id() and no two different
objects can have the same id().

Simple example:

list1 = [ ['one', 'two'], ['one', 'two'] ]

This makes me realise that the spanning tree I brought into the discussion is very likely a red herring. The print (or more generally iteration/visitation) of the structure needs to be curtailed not at an object you already visited, but only at an object that is between you and the root. (In the case of printing or serialisation, that is an object you are part-way through processing.)

Here, you definitely want to visit a three times when printing b:

>>> a = [1, 2, 3]
>>> b = [a, a, a]
>>> b
[[1, 2, 3], [1, 2, 3], [1, 2, 3]]

But after:

>>> c = [4, a, b]
>>> a.append(c)

revisiting a and b is to be avoided during the visit to c

>>> b
[[1, 2, 3, [4, [...], [...]]], [1, 2, 3, [4, [...], [...]]], [1, 2, 3, [4, [...], [...]]]]

However, I'm definitely with Richard that it is the identity of the node that matters, not its value (hashable or not). Of course, I'm assuming I know what kind of iteration Steven wanted, based on the reference to printing (repr).

The question remains whether this can be done as a general capability, and I still see the problem as the inscrutability of built-in types (and their repr, etc.).

Jeff