always new instance?

[Dylan Thurston]

On Tue, Oct 02, 2001 at 01:09:28PM +0300, Cagdas Ozgenc wrote:
> Do I ALWAYS need to create a new instance if I want to modify the state of
> an instance? For example, if I design an index for a simple database with an
> recursive algebric Tree type, do I need to recreate the whole Tree if I
> insert or remove an element? How can I improve performance, what are common
> idioms in these situations?

For trees, if you want to change a node you typically have to recreate
the nodes along the path to the root; that is, all the ancestors of
the node.  If your tree is well-balanced, this is only logarithmic in
the size of your data, and automatically gives you other benefits,
like persistence.

(That is, you only need to change the nodes when the corresponding
subtree has actually changed, which makes some sense.)

I second Mark Carroll's recommendation for Okasaki's book.

Best,
	Dylan Thurston