always new instance?

Mark Carroll mark@chaos.x-philes.com
Tue, 2 Oct 2001 08:01:48 -0400 (EDT)


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