Hi, 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? Thanks
On Tue, 2 Oct 2001, 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?
No, you don't have to copy the whole tree node by node, fortunately: you can "re-use" most of it. I don't fully understand just how good things can get, but I'd heartily recommend Chris Okasaki's "Purely Functional Data Structures" book if you want to. (-: He launches into judging efficiency early on. -- Mark
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
participants (3)
-
Cagdas Ozgenc -
Dylan Thurston -
Mark Carroll