The most balanced case may be the insertion of a element in the middle of a list, but this is far worst than to insert an element in a particular branch of a tree ( it needs an average of list-lenght/2 element creations while in a tree needs only (average-branch-length)/2)<br>
<br>I refer to Maps, because Hashtables, in the IO monad, are mutable. by the way let map2= map1 takes 0 bytes of memory And both do not share side effects, while creating two copies of a hastable to avoid side effects between them needs 2 * size. <br>
<br><div class="gmail_quote">2008/11/18 Tillmann Rendel <span dir="ltr"><<a href="mailto:rendel@daimi.au.dk">rendel@daimi.au.dk</a>></span><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Hello Alberto,<br>
<br>
I cc this to haskell-cafe again.<div class="Ih2E3d"><br>
<br>
Alberto G. Corona wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Not so much memory, because data is referentially transparent, the new Map<br>
can point to whole subtrees of the old map that stay the same. is similar<br>
than when a new list is created by prefixing a new element from a old list<br>
ys= x:xs. ys is not at all a fresh copy, but x plus a pointer to the head<br>
of xs. this is the only new data that is needed to create ys.<br>
</blockquote>
<br></div>
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.<br>
<br>
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.<br><font color="#888888">
<br>
Tillmann<br>
</font></blockquote></div><br>