Type-level type ID

Learn
#1

Is there a way to access a unique type-level ID for each type (maybe by using some GHC built-in)? It’s obviously possible w/ template haskell, but I just used type families to hash the Generic's Meta type, module, and package info into a Nat (compilation times are understandibly horrible).

#3

I don’t think so. To be clear, it sounds like you want

TypeId :: Type -> Nat

where the Nat is distinct for each Type. (You might also want this to be more flexible, so it can deal with e.g. Maybe.) Such a function would be useful in, say, sorting a list of Types into a canonical order.

The problem with such a function is that the universe of types is open. By this, I mean that any module can declare a new type. So there’s no way to guarantee the uniqueness of the number for a type without knowing all the types that are linked together in a program. We could make probably-unique ids by using a hashing function as you describe (built into GHC, so it would be faster).

3 Likes
#4

I’m not completely clear what you are looking for, but does typeRep help? https://www.stackage.org/haddock/lts-17.9/base-4.14.1.0/Data-Typeable.html#v:typeRep

1 Like
#5

Such a function would be useful in, say, sorting a list of Types into a canonical order.

That’s one of the things I wanted to do. I’m also using it to make an archetypal ECS (that needs to be able to combine queries at compile-time and retrieve dynamically typed collections at runtime).

The problem with such a function is that the universe of types is open… So there’s no way to guarantee the uniqueness of the number for a type without knowing all the types that are linked together in a program.

Understandable.

We could make probably-unique ids by using a hashing function as you describe (built into GHC, so it would be faster).

I see. It would definitely be a niche feature! Working on the type families performance issue would probably help more but I have nothing to offer on that front unfortunately.

Thanks for the help!

#6

SomeTypeRep has an Ord instance.

#7

@tomjaguarpaw, I think @whartnett is looking for a type-level solution. Typereps are term-level information.

#8

Is the OP, in effect, describing Idris - a Haskell-type language, where types are first class?

#9

The specific problem here is entirely possible to represent w/ type families, it just compiles extremely slowly. Nonetheless, dependent haskell would be cool!