Hello Alberto, I cc this to haskell-cafe again. Alberto G. Corona wrote:
Not so much memory, because data is referentially transparent, the new Map can point to whole subtrees of the old map that stay the same. is similar than when a new list is created by prefixing a new element from a old list ys= x:xs. ys is not at all a fresh copy, but x plus a pointer to the head of xs. this is the only new data that is needed to create ys.
You could just as well compare with appending a new element to the end of the list, which needs a complete copy of the list structure to be made. One has to look more closely to see which case it is here. More specifically, I do not see how this sharing of substructures could be employed in the implementation of hash tables, which rely on O(1) random access into arrays. Tillmann