[Haskell-beginners] Re: Functional Data Structure with Cheapest Modification?

[Heinrich Apfelmus]

Am 06.04.10 21:31, Travis Erdman wrote:
> In Real World Haskell, the authors state that "the attraction of a
> tree to a functional programmer is cheap modification."  They go on
> to explain that in a tree of say 10,000 nodes, approx 9,985 would be
> reused (on average) when updating a single node (rather than having
> to copy all 10k nodes, like a Haskell list would have to do).
> 
> In my application, I have a collection of (only) about 200 objects.
> So from the surface, not large at all.  However, each object in the
> collection is a large tree that might be up to 20 MB in size.  The
> application pulls objects one at a time from the collection, performs
> some processing, and delivers a new, updated object that needs to be
> inserted in the collection for future processing (the original object
> is now obsolete).  I'm guessing a Data.IntMap might involve copying
> over about 8 objects for each single object update, which while
> better than copying all 200, is still not perfect.

The same reasoning that applies to trees also applies to the objects.
The only thing that will be copied are about log(200) *pointers* to your
objects; the 20MB objects themselves will never be copied.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com