[Haskell-cafe] implementing python-style dictionary in Haskell

[Tillmann Rendel]

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