FiniteMap-like module for unordered keys?
Is there a module that provides functionality similar to that of Data.FiniteMap for keys that do not have a defined ordering relation? (I looked at Data.HashTable, but I couldn't figure why it needs to be implemented in the IO monad, except to optimize the internal implementation. Also, it's not clear to me how it behaves when a key is inserted that already exists.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
On Mon, Nov 08, 2004 at 04:40:58PM +0000, Graham Klyne wrote:
Is there a module that provides functionality similar to that of Data.FiniteMap for keys that do not have a defined ordering relation? Not as far as I know. (Unless you're content with the standard List library's lookup/delete/union/etc)
I don't know if it'd help you, but I'd like to see a FiniteMap which accepts an explicit compare-function instead of requesting it's key-type to be an instance of Ord. One may e.g. want complex numbers in a finitemap (without having to make Complex an instance of Ord), which shouldn't be a problem as an adhoc ordering on Complex is rather trivial to make...
(I looked at Data.HashTable, but I couldn't figure why it needs to be implemented in the IO monad, except to optimize the internal implementation. Also, it's not clear to me how it behaves when a key is inserted that already exists.) A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs... Actually, some kind of freezeHashTable may be useful, and a HashTable in the ST monad is definitely useful: I guess patches are welcome..
Cheers, Remi P.S. If enough people promise to eternally like me for it I might actually do it myself ;) -- Nobody can be exactly like me. Even I have trouble doing it.
Hello,
A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs...
Could you please elaborate? Is there motive why an Hash Table, implemented as FiniteMap of Lists, for instance, wouldn't be worth to using over a simple List? (This wouldn't help G. Klyne of course). I've always wondered why a non-monadic version of is not provided in the GHC libs... J.A.
On Tue, Nov 09, 2004 at 11:41:49PM +0000, Jorge Adriano Aires wrote:
Hello,
A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs... Could you please elaborate? Is there motive why an Hash Table, implemented as FiniteMap of Lists, for instance, wouldn't be worth to using over a simple List? (This wouldn't help G. Klyne of course). I've always wondered why a non-monadic version of is not provided in the GHC libs...
J.A.
I assume you're talking about something like this: {-# OPTIONS -fglasgow-exts #-} {- I want a Hashable instance for String ;) -} import Data.FiniteMap import Data.HashTable (hashInt, hashString) import Data.Int (Int32) class Hashable a where hash :: a -> Hash instance Hashable Int where hash = hashInt instance Hashable String where hash = hashString type Hash = Int32 newtype HashTable a b = HT (FiniteMap Hash [b]) emptyHT :: HashTable a b emptyHT = HT emptyFM addToHT :: (Hashable a) => HashTable a b -> a -> b -> HashTable a b addToHT (HT m) k v = HT $ addToFM_C (flip (++)) m (hash k) [v] Of course one could do that, and it would be (expected) O(log n) instead of O(n), but I doubt I'd really call it a hashtable... It's more like a variant on (Python's?) Decorate-Sort-Undecorate pattern. (Replacing a direct comparison by a conversion to something else which can be compared.) However, it could still be usefull if there will be lots of lookups and comparing elements is expensive. Groetjes, Remi
Ugh, replying to myself... Obviously, the following contains a few mistakes...: On Wed, Nov 10, 2004 at 11:34:32AM +0100, R. Turk wrote:
{-# OPTIONS -fglasgow-exts #-} {- I want a Hashable instance for String ;) -} import Data.FiniteMap import Data.HashTable (hashInt, hashString) import Data.Int (Int32)
class Hashable a where hash :: a -> Hash instance Hashable Int where hash = hashInt instance Hashable String where hash = hashString
type Hash = Int32 newtype HashTable a b = HT (FiniteMap Hash [b]) newtype HashTable a b = HT (FiniteMap Hash [(a,b)])
emptyHT :: HashTable a b emptyHT = HT emptyFM
addToHT :: (Hashable a) => HashTable a b -> a -> b -> HashTable a b addToHT (HT m) k v = HT $ addToFM_C (flip (++)) m (hash k) [v]
addToHT (HT m) k v = HT $ addToFM_C (flip (++)) m (hash k) [(k,v)] -- Nobody can be exactly like me. Even I have trouble doing it.
On Tue, Nov 09, 2004 at 11:41:49PM +0000, Jorge Adriano Aires wrote:
Hello,
A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs...
Could you please elaborate? Is there motive why an Hash Table, implemented as FiniteMap of Lists, for instance, wouldn't be worth to using over a simple List? (This wouldn't help G. Klyne of course). I've always wondered why a non-monadic version of is not provided in the GHC libs...
Sometimes you are willing to pay an arbitrary setup cost for very fast future lookups. for things like symbols tables for instance. This is where a constant non-monadic hash would be quite useful, especially since you know it is immutable you can choose things like the number of buckets more inteligently. or if you wanted to go crazy, generate a perfect-hash on the fly. Binary trees are good at a lot of things, but their memory locality is pretty cruddy for lookups or when your key comparason operator is slow. (I am aware of the absurdity of thinking about memory locality with a dynamic-dispatch STG-machine, but old habits from my Kernel programming days die hard :) ) John -- John Meacham - ⑆repetae.net⑆john⑈
At 16:13 10/11/04 -0800, John Meacham wrote:
... (This wouldn't help G. Klyne of course). I've always wondered why a non-monadic version of is not provided in the GHC libs...
Sometimes you are willing to pay an arbitrary setup cost for very fast future lookups. for things like symbols tables for instance. This is where a constant non-monadic hash would be quite useful, especially since you know it is immutable you can choose things like the number of buckets more inteligently.
Indeed. In a past life, I implemented an IP address translation system where a key requirement was that performance would not degrade as the number of active addresses increased. Performance being very dominated by lookups. The solution adapted an hash table scheme with O(1) lookup characteristics. Insertion/deletion costs were sub O(N), but with a very high constant factor. (The main problem was complexity: the lookup table was a pig to debug!) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
At 23:25 09/11/04 +0100, Remi Turk wrote:
(I looked at Data.HashTable, but I couldn't figure why it needs to be implemented in the IO monad, except to optimize the internal implementation. Also, it's not clear to me how it behaves when a key is inserted that already exists.) A hash-table becomes rather useless without mutable state AFAICS. Without it, one might almost just as well use a list of pairs... Actually, some kind of freezeHashTable may be useful, and a HashTable in the ST monad is definitely useful: I guess patches are welcome..
I can see why using (something like) a state monad might be useful, but not why it needs to be an IO monad, unless there's some fairly low-down optimization being performed. (I'm not asking for this, BTW, just commenting on the apparent lack. For my application, I am using a list of pairs, as I expect these tables to be relatively small.) #g ------------ Graham Klyne For email: http://www.ninebynine.org/#Contact
participants (6)
-
Graham Klyne -
Graham Klyne
-
John Meacham -
Jorge Adriano Aires -
R. Turk -
Remi Turk