[Python-ideas] Tree as a data structure (Was: Graph class)

[Jeff Jenkins]

trying again, this email address was apparently not on the list:

My experience dealing with trees is always that the "tree" part is always
so simple that it isn't a big deal to re-implement it.  The problem is
dealing with all of the extra stuff that you need and the details of what
happens when you do different operations.  I think it makes more sense to
have an interface for a kind of thing you want to do with a tree (e.g.
sorted sets, or ordered maps) rather than the tree itself.



On Wed, Dec 19, 2012 at 10:55 AM, Jeff Jenkins <jeff at jeffreyjenkins.ca>wrote:

> My experience dealing with trees is always that the "tree" part is always
> so simple that it isn't a big deal to re-implement it.  The problem is
> dealing with all of the extra stuff that you need and the details of what
> happens when you do different operations.  I think it makes more sense to
> have an interface for a kind of thing you want to do with a tree (e.g.
> sorted sets, or ordered maps) rather than the tree itself.
>
>
> On Wed, Dec 19, 2012 at 10:11 AM, anatoly techtonik <techtonik at gmail.com>wrote:
>
>> On Sun, Dec 16, 2012 at 6:41 PM, Guido van Rossum <guido at python.org>wrote:
>>
>>> I think of graphs and trees as patterns, not data structures.
>>
>>
>> In my world strings, ints and lists are 1D data types, and tree can be a
>> very important 2D data structure. Even if it is a pattern, this pattern is
>> vital for the transformation of structured data, because it allows to
>> represent any data structure in canonical format.
>>
>> Speaking of tree as a data structure, I assume that it has a very basic
>> definition:
>>
>> 1. tree consists of nodes
>> 2. some nodes are containers for other nodes
>> 3. every node has properties
>> 4. every node has 0 or 1 parent
>> 5. every container has 1+ children
>> 6. tree has a single starting root node
>> 7. no child of a parent can be its ancestor
>>    (no cyclic dependencies between elements)
>>
>> List of trees is a forest. Every subtree is a complete tree.
>>
>>
>> To see which tree data type would be really useful in Python distribution
>> (e.g. provides a simple, extendable and intuitive interface), I see only
>> one way - is to scratching some itches relevant to Python and then try to
>> scale it to other problems. The outcome should be the answer -
>> what for native tree type is not suitable?
>>
>> More ideas:
>> [ ] Much experience for working with trees can be brought from XML and
>> DOM manipulation practices (jQuery and friends)
>>   [ ] every element in a tree can be accessed by its address specificator
>> as 'root/node[3]/last'
>>   [ ] but it is also convenient to access tree data using node names as
>> 'mylib.books[:1]'
>>   [ ] and of course, you can run queries over trees
>>
>> [ ] Tree is the base for any "Data Transformation Framework" as it allows
>> to jump from "data type conversion" to "data structure conversion and
>> mapping"
>>   [ ] Trees can be converted to other trees and to more complicated
>> structures
>>   [ ] Conversion can be symmetrical and non-symmetrical
>>   [ ] Conversion can be lossy and lossless
>>   [ ] Conversion can be lossless and non-symmetrical at the same time
>>
>> Trees can be used, for example, for realtime migration of issues from one
>> tracker to another. For managing changesets with additional meta
>> information. For presenting package dependencies and working with them. For
>> atomic (transactional) file management. For managing operating system
>> capability information. For logging setup. For debugging structures in
>> Python. For working and converting binary file formats. For the common AST
>> transformation and query interface. For the understanding how 2to3 fixers
>> work. For the common ground of visual representation, comparison and
>> transformation of data structures. That's probably enough of my itches.
>>
>> _______________________________________________
>> Python-ideas mailing list
>> Python-ideas at python.org
>> http://mail.python.org/mailman/listinfo/python-ideas
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20121219/54f0445c/attachment.html>