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

[Alberto G. Corona]

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 <rendel at daimi.au.dk>

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20081118/48474a3e/attachment-0001.htm