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://en.wikipedia.org/wiki/Recursion https://www.cs.utah.edu/~germain/PPS/Topics/recursion.html 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 = []     >>> x.append(x)     >>> x     [[...]]     >>> x[0] is x     True

So far as I know, it's not possible to create such using only immutable objects. And anything created using only immutable objects will have a hash.

A beginner can easily by mistake create an object such as x above, and without the short-circuit provided by     >>> x     [[...]] the result is an unprintable object, that further raises an exception (or worse). That's really bad for the poor beginner.

As a first approximation, my opinion is that data having such a loop / cycle in it is at least a code smell, and perhaps worse. However, there may be examples that I've not considered that would make me change my mind.

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 tuple of the node and the distance). This naturally creates a recursive structure unless connections are unidirectional and the graph is acyclical (i.e. a tree). For example, a 3 node fully connected graph might be: a = [] b = [] c = [] a.append(b) a.append(c) b.append(a) b.append(c) c.append(a) c.append(b) Maybe more generally the nodes would be dicts of properties, one of which is a connection property with that list of nodes, but you still end up with the same recursion.

By the way, in the mathematics of the symmetric group (permutations) the two tuples     >>> (0, 1, 2, 3)     >>> (1, 2, 3, 0) are different representations of the same cycle (where here the word cycle has a different meaning).

Also by the way, determining if two vertex-edge graphs are isomorphic is a hard problem. I've been told that the best tool for this is https://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml https://www3.cs.stonybrook.edu/~algorith/implement/nauty/implement.shtml

To summarise, it's loops / cycles in the representation of the data that's the problem. Without a use case to the contrary, I'd say don't do this. That's my opinion. Yours may be different.

Final idea. Perhaps a tool to detect cycles in data might be a good idea.

Finally, Happy New Year.

 --  Jonathan

-- Richard Damon

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 adding to that collection the nodes that are adjacent (or maybe a tuple of the node and the distance). This naturally creates a recursive structure unless connections are unidirectional and the graph is acyclical (i.e. a tree).

For example, a 3 node fully connected graph might be:

a = [] b = [] c = []

a.append(b) a.append(c) b.append(a) b.append(c) c.append(a) c.append(b)

 According to https://en.wikipedia.org/wiki/Graph_theory#Graph https://en.wikipedia.org/wiki/Graph_theory#Graph, a graph is an ordered pair

...

...

...

G = (V, E) where V is a set of vertices, and E is a set of edges, where an edge is an unordered pair of vertices.

You've given the complete graph on 3 vertices (although without explicitly stating the vertex set V).  https://en.wikipedia.org/wiki/Complete_graph https://en.wikipedia.org/wiki/Complete_graph

If we use the wikipedia definition (with vertices 'a', 'b' and 'c') we have

...

...

...

V = {'a', 'b', 'c'} E = {{'a', 'b'}, {'a', 'c'}, {'b', 'c'}}

I've shown how to represent graphs, by directly translating the mathematical definition into Python (without introducing any additional classes). You've produced a different way to represent graphs.

Mathematically, your representation is this. There is a set V of vertices. Further, for each v in V there is associated a subset V_v of V. Further, if w in V_v then v in V_w.

I wouldn't call what you've written down the Python representation of this mathematical definition. To explain this, I'll write down what I think it should be.

Suppose G is a graph with vertices {'a', 'b', 'c', 'd'}. Using a dict to represent the map that v goes to V_v, we can write G as {     'a': {...},     'b': {...},     # etc     'e': {...}, }

My initial post suggests that, purely on the basis of the loop in the data structure, there's a code smell in the representation you provided. I'd say that not agreeing with its own mathematical definition is a code smell (or worse).

I'll put it another way. Suppose our vertices are called (or represent) Alice, Bob, Carol, Dave and Eve. Now let G be the graph whose edges represent the existence of cryptographically secure communication between X and Y. I claim that your code isn't able to represent such a graph.

Thank you Richard for forcing me to think things through and find what I consider to be a flaw in the code you supplied.

--  Jonathan

This may be the practical difference betwen Theory and Practice (which in Theory doesn't exist). There are times when processing a system that can be represented as a graph, it is cleanest to think first of node, and then by their connections. Your notation makes it inconvenient that given you are at node A to know what nodes it connects to,  you need to search through the E structure to find all entries with the starting node listed. You also get the 'name' of the node, not the node itself, so you need another dictionary to map names to the actual nodes them selves (where more information about the node might be stored). Yes, maybe in pure graph theory all this isn't important, but if I am USING a grahph for actual work, it might be. Also, your example assumes that NAMES are the important piece, how would you build your structure if names do not exist or are not unique, Once you make the node themselves important, then making the links by the node itself instead of by some arbitrary name makes sense. Also, if the graph is directed, like Alice has a way to drop a message into Bobs secure storage box, but Alice doesn't have access to one of her own, so Bob can't use that method to send back to Alice, then it can make sense to make the edge list not a total separate structure, but each node includes the edges it can talk to itself. It can be noted that this is very much like the model of the internet as it exists today. Every machine (a node), keeps track of who it can directly talk to, and a list of who it is next to and guess for who it should try to send messages to in order to get a message to somone it is not next to. There is no master list of edges in existance anywhere (I once did see a master listing of the graph of the network in the early days before automatic routing, such a map would be impossible to build today). Once you move the listing of links into the node itself, as opposed to having a separate listing of all the vertices, and make the links to node rather than names (to avoid an extra unneeded lookup) then you get the recursive data structure. For your example you say that can not be represented, let us build a graph G as a dictionary, with the key being the name and the value being the 'Node' for that person. (This assumes names are unique, otherwise it might just need to be a list) That node will be a dictionary, where we can store all sorts of properties, but lets define one with a key 'secure' that has as its value a listing of all the nodes this node knows how to directly send to. Thus we could define the graph as: g = {   'Alice': {'secure': []},   'Bob': {'secure': []},   'Carol': {'secure': []},   'Dave':, {'secure': []}.   'Eve':, {secure': []}, } now we can add connections with something like: g['Alice']['secure'].append(g['Bob']) Note that this structure doesn't really even need g to exist at all, it is only needed to initially find the nodes, the nodes could easily be independent variables, or perhaps different nodes are in different structures if they are obtained from different sources. (Node likely will have a property in them to provide a human recognizable name for them). Yes, perhaps at this point it might make sense to make the nodes an actual class as opposed to just a dict, which sort of breaks the cycle as by default __repr__ and such don't expand through class objects, but that then changes the mindset from a data-driven to an object based design, and depending what else the program needs to interface to one or the other might be more complicated. -- Richard Damon

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, and nicely disagreeing with me. However, the problem of 'walking a graph' to find a spanning tree is first of all a matter of choosing an algorithm. The algorithm to be used and the representation of the graph are two different matters. Suppose the vertices are well ordered, for example (0, 1, 2, 3, .., n). Write each edge as an ORDERED pair, with the first vertex being less than the second vertex. Now list the edges in lexicographic order. That solves the problem, and gives a unique representation, provided we are given a well ordering of the vertices. Under certain circumstances, we can use the Python id to provide the well ordering of vertices. However, that doesn't always work. Two strings (or large ints, or tuples) can be equal even though they have different ids. However, I think it reasonable to assume that we have a sensible equality relation on the vertices. Now things get interesting. For a very large graph, it would be very helpful if every vertex has a hash. This would make determining equality easier. But if the data structure representing the graph has Python cycles in it (as in Steven's use case) then there won't be a hash available. Do you agree with me, Jeff, that the problem of printing out a vertices-and-edges graph is much easier (or at least quicker) if each vertex has a hash. More exactly, we want a quick and easy way to determine if two vertices are equal. It would be nice to have some further input from Steven, whose original post stated the problem he wished to solve. -- Jonathan

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. In other words, as stated earlier, things are easier and quicker if the nodes are hashable. Only hashable objects can be stored in a set, and equality of NODE doesn't imply equality of ID. (The converse is trivially true.) Here's an example >>> def f(): return 10**1000 >>> list(map(id, (f(), f()))) [139927013695536, 139927013696008] By the way, this surprised me. Would anyone like to explain this? >>> id(f()), id(f()) (139927013695536, 139927013695536) -- Jonathan

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, 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

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 exists. Here the object returned by the first call is discarded after its id is taken. Then the second object is created and reuses the memory address that was used by the first object. Since in CPython id() returns object's memory address, the id's are the same.

What Eric said, except I would put more emphasis on two things: 1. I would emphasize more strongly that IDs are abstract identity numbers, not memory addresses except as an accident of implementation. For example in Jython and IronPython, the IDs are sequential numbers and won't be reused. In general, if the Python implementation is using a compacting garbage collector where objects can move in memory, IDs cannot be memory addresses. 2. And that it's a matter of happenstance, not design, that the same memory address happens to be used. I can't produce a demonstration right now, but I've seen senarios where every *second* temporary object reuses the previous IDs, so printing a sequence of IDs goes something like this: 1012, 1042, 1012, 1042, 1012, 1042 ... Presumably that could happen if the garbage collector takes longer to reclaim each temporary object than it takes the interpreter to generate and process the next one. -- Steve

Bravo, Jeff. I couldn't have chosen a better example. However, I'd expect large ints to be stored in two parts. A (class, pointer) pair which has fixed size. And memory referenced by the pointer, large enough to store the value of the large int. However, that's part of the language implementation, and not part of the language definition. -- Jonathan

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 the structure, not just get a flat list of nodes.

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__| ?

I don't think so. All the logic for dealing with cycles is buried inside pickle -- __getstate__ just gets info about one object. -- Greg

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 that there aren't significant savings. On 1/1/21 7:38 PM, Samuel Freilich via Python-ideas wrote:

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 only O(n*d) where d is the nesting depth, not O(n^2)): https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a09... https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a09...

copy.deepcopy keeps track with a dict: https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a09... https://github.com/python/cpython/blob/3bf05327c2b25d42b92795d9d280288c22a09...

(That uses a sentinel object as the default for the lookup so it can tell if that's explicitly set to None, though that seems convoluted compared to just checking whether the value is None or not. Is that considering that "copy.deepcopy(x) is None and x is not None" might be true?)

Peace, -Sam

On Fri, Jan 1, 2021 at 7:07 PM Greg Ewing mailto:greg.ewing@canterbury.ac.nz> wrote:

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 the structure, not just get a flat list of nodes.

> 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__| ?

I don't think so. All the logic for dealing with cycles is buried inside pickle -- __getstate__ just gets info about one object.

-- Greg

-- Richard Damon

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 out and provide as a tool or recipe for people to use in their own code?

It sounds promising but so far a bit too vague for me to understand what you're really suggesting.

It is vague to me too, and I don't really have any concrete suggestions. I was hoping to start a discussion that might lead to some concrete suggestions. -- Steve