[Haskell-cafe] Re: [Haskell] Re: Global Variables and IOinitializers

[John Meacham]

On Mon, Nov 29, 2004 at 03:09:53PM -0000, Simon Peyton-Jones wrote:
> | > In fact GHC at least *already* generates a unique integer for each
> | > TypeRep. A good idea, since it means comparisons can be done in unit
> | > time. Thus indexing can be done trivially using this integer as a
> | > hash function.
> | 
> | Yes, I have seen this in the code, too. The Ord and Typeable instances
> | should be trivial.
> 
> Take care here.  There is no guarantee that the unique number generated
> will be the same in each run.  So if you have Ord Typeable, this program
> may give unpredictable results:
> 
> main = print (typeOf True < typeOf 'x')
> 
> 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

I thought it would be good to have two Ord classes, one to give the
natural ordering (Ord) if one exists, and one to give the most efficient
one for implementing maps/sets which has the side constraint that
nothing may observably depend on what the actual order is, just that it
is a valid total ordering. I have come across a few types where such a
distinction would have been nice to have. either because the ordering
was arbitrary so exposing it via 'Ord' seemed like a white lie to the
user or a much more efficient yet non-intuitive ordering was possible..

of course, the side condition here is pretty vauge. I don't know how to
enforce it within the type system, but it is a pretty straightforward
condition which I don't think would cause too much trouble in practice
to maintain.

        John

-- 
John Meacham - ⑆repetae.net⑆john⑈