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)
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. 2008/11/18 Tillmann Rendel <[EMAIL PROTECTED]> > 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 >
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
