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