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⑈