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⑈

On Mon, 29 Nov 2004, Simon Peyton-Jones wrote:

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 was going to ask what was wrong with doing the tedious: class FiniteMappable key where listToFM :: [(key,elt)] -> FiniteMap key elt addToFM :: FiniteMap key elt -> key -> elt -> FiniteMap key elt ...etc etc... with the possibility of: instance Ord key => FiniteMappable key where listToFM = listToFMoriginal ...etc etc... where one would only export the fact that a particular type is FiniteMappable, not Ord. But then I remembered that modules can't hide instance declarations, so that's no good. :-( Is there some way to insert a newtype, so that just one instance becomes visible? -- Ian Stark http://www.ed.ac.uk/~stark LFCS, School of Informatics, The University of Edinburgh, Scotland