A dictionary implementation in Hasekll
Does anybody knows of an implementation for an efficient dictionary (such as a hash, an AVL tree, a B-Tree etc. ) in Haskell? Can an array do that? I'd like something that can map any type to any other type based on a comparison function, and perhaps a hashing function. TIA, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish shlomif@vipe.technion.ac.il Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: shlomif@techie.com The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one.
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 QRCZAK
participants (2)
-
qrczak＠knm.org.pl -
Shlomi Fish