FiniteMap performance WITHOUT any copying?

[Zdenek Dvorak]

Hello,

>Now, Haskell has a garbage collector, so Haskell must know how many
>pointers there are to all objects in the heap (or?). Then, if a finite map
>for example only has one single pointer to it, then it ought to be all
>right to modify the finite map (or whatever datastructure we are
>considering), I mean really modify the map without making any copies, just
>like in imperative languages. Perhaps there might be pointers to nodes
>inside the tree and I guess that could complicate the matter somewhat. But
>for Haskell arrays it ought to be possible to really modify the array if
>it is used by only one pointer ?
>
>Are such optimizations possible, and if they are, are they already
>implemented in for example GHC ? Or am I wrong somewhere ?

You are more or less right; except that
-- the Haskell implementations I have seen do not keep number of pointers to
objects (gc in principle works by traversing the graph made by pointers,
marking reachable nodes and finally removing the unreachable ones; just
keeping the number of references is not sufficient due to cyclic structures)
-- due to lazy evaluation, the situation where there would be just one
pointer to array is rare

Zdenek

_________________________________________________________________
Add photos to your messages with MSN 8. Get 2 months FREE*. 
http://join.msn.com/?page=features/featuredemail