RE: Efficient or predictable Ord for Typeable
The trouble is that *any* "function" can now deliver unpredictable results. Can I rely on the fact that foo :: Int -> Int will always give the same answer given the same input. Not any more. I think the strongest argument here is that it's like a more benign version of unsafePerformIO, whose existence also threatens foo's predictability. | -----Original Message----- | From: George Russell [mailto:ger@informatik.uni-bremen.de] | Sent: 30 November 2004 09:55 | To: haskell-cafe@haskell.org; Simon Peyton-Jones; John Meacham | Subject: Efficient or predictable Ord for Typeable | | Simon PJ wrote (snipped): | > This unfortunate observabilty of an ordering (or hash value) that is | > needed only for efficient finite maps, is very annoying. I wish I knew | > a way round it. As it is we can pick | > a) expose Ord/Hash, but have unpredictable results | > b) not have Ord/Hash, but have inefficient maps | | In this case there is a simple solution. Simply define | | newtype FastUnpredictableInstances a = FastUnpredictableInstances a | | and define the fast Ord and Hash only for FastUnpredictableInstances. | People who manage to type all that then have no grounds to grumble | if they get bitten. For something as basic as implementing execution | contexts, FastUnpredictableInstances is acceptable.
Simon Peyton-Jones wrote:
The trouble is that *any* "function" can now deliver unpredictable results. Can I rely on the fact that foo :: Int -> Int will always give the same answer given the same input. Not any more.
Yes, I see what you mean.
I think the strongest argument here is that it's like a more benign version of unsafePerformIO, whose existence also threatens foo's predictability.
I suggest you implement hashTypeable :: Typeable -> IO Int32 This would be just as useful for global variables/execution contexts as allowing a hash function which doesn't mention IO, but still preserves determinacy for foo :: Int -> Int. Determinacy for foo :: Int -> IO Int won't be preserved, but then of course you didn't have it in the first place, even with Haskell 98. If there were a Hash class (I think there should be), then it might in general be a good idea to define it by
class Hash a where hash :: a -> IO HashInt
You don't need a pure function for this after all.
George Russell wrote:
Simon Peyton-Jones wrote:
The trouble is that *any* "function" can now deliver unpredictable results. Can I rely on the fact that foo :: Int -> Int will always give the same answer given the same input. Not any more.
Yes, I see what you mean.
I think the strongest argument here is that it's like a more benign version of unsafePerformIO, whose existence also threatens foo's predictability.
I suggest you implement
hashTypeable :: Typeable -> IO Int32
And/or mkHashTypeable :: IO (Typeable -> Int32) -- Lennart
On Tue, 30 Nov 2004, Lennart Augustsson wrote:
George Russell wrote:
I suggest you implement
hashTypeable :: Typeable -> IO Int32
And/or mkHashTypeable :: IO (Typeable -> Int32)
And/or (you'll hate this): mkHashTypeable :: ACIO (Typeable -> Int32) After all, I'm sure you don't want hasTypeable / mkHashTypeable to give different answers when used twice on the same run. Simon Peyton-Jones wrote:
The trouble is that *any* "function" can now deliver unpredictable results. Can I rely on the fact that foo :: Int -> Int will always give the same answer given the same input. Not any more.
Performing a dubious toplevel 'declare hashTypeable <- mkHashTypeable' hits an odd middle ground here: you can indeed rely on the fact that foo :: Int -> Int will always give the same answer given the same input, anywhere in the program. It just won't necessarily give the same answer next time you run the program. No call-by-name rewrites are broken, but something is certainly strange. -- Ian Stark http://www.ed.ac.uk/~stark LFCS, School of Informatics, The University of Edinburgh, Scotland
(me)
I suggest you implement
hashTypeable :: Typeable -> IO Int32
Lennart wrote (snipped)
And/or mkHashTypeable :: IO (Typeable -> Int32)
Although this is OK, a general hash function might well need to return IO HashKey. A while back, before Data.Unique, I implemented a Unique module with interface: newUnique :: IO Unique uniqCompare :: Unique -> Unique -> IO Ordering The values returned by uniqCompare are guaranteed to be consistent. This implementation (which was not meant terribly seriously) was unusual because it did not use unsafePerformIO or any other global state, though it did need MVars and access to the current thread identifier (if in a concurrent world). The ordering was constructed dynamically as you called uniqCompare. The source is here: http://www.mail-archive.com/glasgow-haskell-users@haskell.org/msg01109/Uniqu... Converting the function to be of type getUniqCompare :: IO (Unique -> Unique -> Ordering) would be impossible. I suspect there may be other cases where you dynamically construct a hash function.
participants (4)
-
George Russell -
Ian.Stark＠ed.ac.uk -
Lennart Augustsson -
Simon Peyton-Jones