Trees

Terry Reedy tjreedy at udel.edu
Wed Jan 21 03:19:07 CET 2015


On 1/20/2015 4:47 PM, Mario wrote:
> In article <d34dbfbe-fe82-47dc-8bc3-c8773e2b70dd at googlegroups.com>,
> rustompmody at gmail.com says...
>>
>> Yeah python has trees alright.
>>
>> Heres' some simple tree-code
>
> Didn't you just demonstrate that Python has no trees and instead you
> have to implement them yourself (or use a third-party implementation)?
>
> I don't know what's the point of all this vain and misleading play with
> words.

It is not play with words. A tree is a recursive - nested - hierachical 
data structure with the restriction of no cycles or alternate pathways. 
  Python collections whose members are general objects, including 
collections, can be nested.  The resulting structures *are* tree 
structures, if not more general directed graphs.  They are quite 
commonly used in Python.

The common question -- "How do I flatten a list" -- is asking "How to I 
turn a list from a tree (or DAG, but not a cyclic graph*) into a 
sequence of leaf objects".  The question illustrates what is missing - 
builtin functions or methods for nested collections.  I already 
suggested that there *might* be a useful addition in this direction.

* A Python interpreter needs to take special measures to even display an 
infinitely recursive list without raising or even segfaulting.  Most 
posted 'flatten' functions do not account for this possibility.

 >>> l = [1]
 >>> l.append(l)
 >>> l
[1, [...]]


 > Not only most languages don't implement trees in their standard
> libraries

Typically, built-in collection type C has members of type M that does 
not include type C.  Therefore a C instance cannot (directly) contain a 
C instance.  The result is that people write a 'design pattern' to 
overcome the limitation and enable a C to indirectly include a C.  Since 
this limitations does not exist in Python's generalized collections of 
objects, the pattern is unneeded in Python.

-- 
Terry Jan Reedy




More information about the Python-list mailing list