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