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

[anatoly techtonik]

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-ideas/attachments/20121219/3f962fb7/attachment.html>