No trees in the stdlib?

[João Valverde]

Paul Rubin wrote:
> João Valverde <backup95 at netcabo.pt> writes:
>   
>> Could you clarify what you mean by immutable? As in... not mutable? As
>> in without supporting insertions and deletions?  
>>     
>
> Correct.  
>
>   
>> That's has the same performance as using binary search on a sorted
>> list.  What's the point of using a tree for that?
>>     
>
> The idea is you can accomplish the equivalent of insertion or deletion
> by allocating a new root, along with the path down to the place you
> want to insert, i.e. O(log n) operations.  So instead of mutating an
> existing tree, you create a new tree that shares most of its structure
> with the old tree, and switch over to using the new tree.  This
> trivially lets you maintain snapshots of old versions of the tree,
> implement an "undo" operation, have a background thread do a complex
> operation on a snapshot while the foreground thread does any number of
> update-and-replace operations, etc.
>
>
>   
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", undo is kind of redundant and multithreading... 
don't see a compelling use that would justify it. Also the interface is 
a mapping so it'd be rather nice to emulate dict's.

Have you considered how the syntax would work in Python by the way? This:

new_tree = old_tree.insert(object)

Just looks wrong. The interface should support non functional idioms too.