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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
