unique id for data types

[Stefan O'Rear]

On Tue, Sep 18, 2007 at 04:41:33PM +0100, Barney Hilken wrote:
> Hi Simon, thanks for the response.
>
> In fact I really only need NameCmp to be defined for datatypes of the form
> 	data T = T
> but it's still a lot, so I was expecting to need an extension. Lexical 
> comparison of fully qualified names is what I had in mind, but I wanted 
> some confirmation that such things exist!
>
> I could post a GHC feature request, but unless I get someone else 
> interested in this, it would probably just sit in Trac indefinitely. Where 
> should I look in the ghc source if I want to add it myself?

As usual, Oleg solved this problem long ago.  I don't remember a
citation, but the gist of the procedure is:

data HCons a b
data HNil

type family TTypeOf a :: *

type instance TTypeOf Int = ...ascii code for 'I' 'n' 't' represented
                               using HCons/HNil...
...


type family Combine a b :: *
type instance Combine LT a = LT
type instance Combine EQ a = a
type instance Combine GT a = GT

type family NumCmp a b :: *
type instance NumCmp HNil HNil = EQ
type instance NumCmp HNil (HCons a b) = LT
type instance NumCmp (HCons a b) HNil = GT
type instance NumCmp (HCons a b) (HCons c d) =
    Combine (NumCmp a c) (NumCmp b d)

type family TypeCmp a b :: *
type instance TypeCmp a b = NumCmp (TTypeOf a) (TTypeOf b)



The O(n) remaining instances can be automated with my
Data.Derive.TTypable, if you're willing to switch back to functional
dependancies.  (Simon, can a TF 'wrapper' for a fundep be meaningfully
done?)

Stefan
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/glasgow-haskell-users/attachments/20070918/5095e12a/attachment.bin