[Haskell-cafe] implementing python-style dictionary in Haskell
rendel at daimi.au.dk
Tue Nov 18 06:46:47 EST 2008
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.
More information about the Haskell-Cafe