Thanks to everybody for the great replies!

>Sharing is the key.  The beauty of immutable data structures is that
>sharing is always safe.

Ah, this makes sense.  How does the compiler "know" the datastructure is purely functional?  In other words, is there any way for me to get a type into a tree that has a mutable member (perhaps through an abstract type), and if so, what happens in that case?

Chris