A dictionary implementation in Hasekll

Marcin 'Qrczak' Kowalczyk qrczak@knm.org.pl
7 Jan 2001 21:25:58 GMT

Sun, 7 Jan 2001 20:00:51 +0200 (IST), Shlomi Fish <shlomif@vipe.technion.ac.il> pisze:

> Does anybody knows of an implementation for an efficient dictionary
> (such as a hash, an AVL tree, a B-Tree etc. ) in Haskell?

ghc's library contains FiniteMap, implemented as a balanced binary tree
(not exactly AVL), over any comparable type as the key.

I haven't seen a hash table. It's harder to do in the functional
context. It would either have to be mutable, or provide bulk operations
on many elements at once to be efficient - or use a trick with hidden
mutations in place to obtain a modified value while substituting
a backward difference for the old value, to have the functional
interface and cheap access to newest versions.

 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
  ^^                      SYGNATURA ZASTĘPCZA