In order to make my records system practically useable, I need a type family
type family NameCmp n m
which totally orders datatypes. More precisely, it should return one of the following types:
data NameLT = NameLT data NameEQ = NameEQ data NameGT = NameGT
for each pair of datatypes n & m, according to whether n < m, n = m, or n > m in some global ordering. This ordering needs to be independent of the context, so it can't be affected by whatever imports there are in the current module. What I want to know is: does GHC give datatypes any global id I could use to generate such an ordering? Would fully qualified names work? Secondly (assuming it's possible) how easy would it be for me to write a patch to add NameCmp to GHC? Where in the source should I start looking? Thanks, Barney.
You're asking for something tricky here. | > type family NameCmp n m | | which totally orders datatypes. More precisely, it should return one | of the following types: | | > data NameLT = NameLT | > data NameEQ = NameEQ | > data NameGT = NameGT Now, whenever you declare a new data type T, you want, magically, the following instances to spring to life type instance NameCmp T Int = NameLT type instance NameCmp T Bool = NameLT ..etc etc etc... Obviously there would be way too many instances. So you really want a built-in magic type family NameCmp, which does what you want. Furthermore, the behaviour should be predicatable across compilers; so you'd need to specify just what the result should be in a compiler-independent way. Well I suppose you might do that (via lexical comparison of fully-qualified names), but it's clearly An Extension. Type-families alone get nowhere near. Simon
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? Barney.
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
Hi Stefan, That's great! Where can I get hold of your TTypable? It's not in Hackage and Google didn't find it. I don't know where else to look... Barney.
On Tue, Sep 18, 2007 at 10:10:31PM +0100, Barney Hilken wrote:
Hi Stefan,
That's great! Where can I get hold of your TTypable? It's not in Hackage and Google didn't find it. I don't know where else to look...
Barney.
Start by fixing the typo, sorry. http://www.google.com/search?q=ttypeable My deriver is #1, and the original is page 34 of #7. Stefan
Ah! your link lead me to the HList paper, where all questions are answered... Thanks, Barney.
Well done Stefan, for reminding us that it can be done today without the magic. Still it's kind-of-inefficient to encode the name of the type constructor that way. There's a case for adding some built in constants at the type level (numbers, strings) and operators over them. Simon | -----Original Message----- | From: glasgow-haskell-users-bounces@haskell.org [mailto:glasgow-haskell-users-bounces@haskell.org] On | Behalf Of Barney Hilken | Sent: 18 September 2007 23:29 | To: Stefan O'Rear | Cc: glasgow-haskell-users@haskell.org | Subject: Re: unique id for data types | | Ah! your link lead me to the HList paper, where all questions are | answered... | | Thanks, | | Barney. | | _______________________________________________ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Ok, I'm stuck. The Oleg stuff is great, and it looks like he did everything I've done long ago, without needing type functions or associated types. But I can't use the TTypeable stuff directly because you can't convert the "relational" style of Oleg's work (using functional dependencies) to the "functional" style I'm using (using type families). Rewriting all the basics in my style is no problem (especially as I only need a limited part of it) EXCEPT Derive depends on (at least the types of) Template Haskell, and TH can't define type family or associated type instances. So I'm back where I started. Barney.
participants (3)
-
Barney Hilken -
Simon Peyton-Jones -
Stefan O'Rear