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

[Tillmann Rendel]

kenny lu wrote:
> Internally, python dictionary is implemented using hash table.
> 
> My first attempt is to use Data.HashTable. However it was immediately
> abandoned, as I realize the memory usage is unreasonably huge.

Why should a Haskell hash table need more memory then a Python hash 
table? I've heard that Data.HashTable is bad, so maybe writing a good 
one could be an option.

> Python dictionary allows for update. e.g. the statement
> d['a'] = 3
> changes the value pointed by 'a' from 1 to 3.

I understand "changes" in the sense of an destructive update: The hash 
table stays the same (in terms of "object identity"), but the content of 
the memory cell storing the value of d['a'] is changed in place. That 
means that the old hash table, with d['a'] == 1, doesn't exist anymore.

> -- the Dict type class
> class Dict d k v | d -> k v where
>     empty :: d
>     insert :: k -> v -> d -> d
>     lookup :: k -> d -> Maybe v
>     update :: k -> v -> d -> d

But here you want to create a new d, e.g. a whole new hash table, which 
contains mostly the same content, but one memory cell different. The old 
hash table still exists in memory. That is a totally different operation 
which is quite likely to need more memory.

   Tillmann