[Haskell-cafe] implementing python-style dictionary in Haskell
rendel at daimi.au.dk
Tue Nov 18 07:27:06 EST 2008
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.
More information about the Haskell-Cafe