No trees in the stdlib?

João Valverde backup95 at
Mon Jun 29 17:54:38 EDT 2009

João Valverde wrote:
> Paul Rubin wrote:
>> João Valverde <backup95 at> writes:
>>> Interesting, thanks. The concept is not difficult to understand but
>>> I'm not sure it would be preferable. A copy operation should have the
>>> same cost as a "snapshot",     
>> You mean a deep-copy?  That is unnecessarily expensive; with a
>> functional structure you can snapshot (or copy) by copying a single
>> pointer.
> Shallow copy...
>>> undo is kind of redundant and multithreading... don't see a
>>> compelling use that would justify it.     
>> Here is one:
> I just skimmed that but if someone really needs multithreading for 
> such intensive processing without wanting a database, fair enough I 
> guess.
>>> Have you considered how the syntax would work in Python by the way? 
>>> This:
>>> new_tree = old_tree.insert(object)
>>> Just looks wrong.     
>> It looks fine to me.  Obviously you could support a wrapper with
>> a mutating slot that holds a pointer to the tree.
> I didn't get the last part, sorry. But I think you'd have a lot of 
> users annoyed that the interface is similar to a list yet their 
> objects mysteriously disappear. To me, tree.insert() implies 
> mutability but I defer that to others like yourself with more 
> experience in Python than me.

Rereading this I got what you meant by "wrapper with mutating slot".  
But that is (like I think you implied) functionally equivalent to a 
mutating data structure, with worse performance because of additional 
memory allocation and such. Is it faster to rebalance the tree with a 
persistent data structure?

More information about the Python-list mailing list