[Tutor] named list

[spir]

Hello, python world!

I'm looking for a way to implement a kind of "named" list, or named tree, with the following requirements:

* Each item is named (or key-ed), like in a dict.
* Each item (node) can be either a terminal item (leaf) or a sub-list (branch).
* There may be items with the same name, unlike in a dict.
* The item entering order is preserved, unlike in a dict.

* A non-requirement: may be useful that items can be retrieved by name (in case several items have the same name, it's allright to return first one -- it's up to the client code to manage that)

A structural representation of such an object looks like that:

obj
	n1:val
	n2:val
	n3
		n31:val
		n32
			n321:val
			n322:val
		n33
	n4

Which is exactly the same as for a list, except that each item gets a name in addition to its value.
I ask for advices before doing bull**** as I suspect there may be a data structure in language theory that matches that needs. Some questions:

* Do you know of such a structure?
* What is the difference between a tree and a python list? a tree and an array that allows nesting?
* Are items in a tree, as defined in theory, supposed to be of homogeneous type?

I cannot implement that simply by giving items an additional attribute, for items can be of an type and can even change. They also need a whole bunch of custom methods. This would require sub-typing averu possible type, including custom ones (this was the cause of a previous, in which I asked if it was possible to sub-type at a type known at runtime). So I plan instead to implement the whole load of necessary behaviour in a container, thus letting the items unchanged.
A possible design (?) would be to subtype list in order to add such a container object a parallel list of names. So that direct access still directly reaches values, while matching names are accessed by indexing a parallel list:

	obj[n] <-- item
	obj.names[n] <-- name

And maybe:

	obj.link[n] <-- (name,item)
	obj[name] <-- item
	obj.name(item) <-- name

Denis

------
la vida e estranya