Is it possible to get the Kind of a Type Constructor in Haskell?

Question

I am working with Data.Typeable and in particular I want to be able to generate correct types of a particular kind (say *). The problem that I'm running into is that TypeRep allows us to do the following (working with the version in GHC 7.8):

let maybeType = typeRep (Proxy :: Proxy Maybe)
let maybeCon = fst (splitTyConApp maybeType)
let badType = mkTyConApp maybeCon [maybeType]

Here badType is in a sense the representation of the type Maybe Maybe, which is not a valid type of any Kind:

> :k Maybe (Maybe)

<interactive>:1:8:
    Expecting one more argument to ‘Maybe’
    The first argument of ‘Maybe’ should have kind ‘*’,
      but ‘Maybe’ has kind ‘* -> *’
    In a type in a GHCi command: Maybe (Maybe)

I'm not looking for enforcing this at type level, but I would like to be able to write a program that is smart enough to avoid constructing such types at runtime. I can do this with data-level terms with TypeRep. Ideally, I would have something like

data KindRep = Star | KFun KindRep KindRep

and have a function kindOf with kindOf Int = Star (probably really kindOf (Proxy :: Proxy Int) = Star) and kindOf Maybe = KFun Star Star, so that I could "kind-check" my TypeRep value.

I think I can do this manually with a polykinded typeclass like Typeable, but I'd prefer to not have to write my own instances for everything. I'd also prefer to not revert to GHC 7.6 and use the fact that there are separate type classes for Typeable types of different kinds. I am open to methods that get this information from GHC.

Answer 1

We can get the kind of a type, but we need to throw a whole host of language extensions at GHC to do so, including the (in this case) exceeding questionable UndecidableInstances and AllowAmbiguousTypes.

{-# LANGUAGE KindSignatures #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE PolyKinds #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE AllowAmbiguousTypes #-}

import Data.Proxy

Using your definition for a KindRep

data KindRep = Star | KFun KindRep KindRep

we define the class of Kindable things whose kind can be determined

class Kindable x where
    kindOf :: p x -> KindRep

The first instance for this is easy, everything of kind * is Kindable:

instance Kindable (a :: *) where
    kindOf _ = Star

Getting the kind of higher-kinded types is hard. We will try to say that if we can find the kind of its argument and the kind of the result of applying it to an argument, we can figure out its kind. Unfortunately, since it doesn't have an argument, we don't know what type its argument will be; this is why we need AllowAmbiguousTypes.

instance (Kindable a, Kindable (f a)) => Kindable f where
    kindOf _ = KFun (kindOf (Proxy :: Proxy a)) (kindOf (Proxy :: Proxy (f a)))

Combined, these definitions allow us to write things like

 kindOf (Proxy :: Proxy Int)    = Star
 kindOf (Proxy :: Proxy Maybe)  = KFun Star Star
 kindOf (Proxy :: Proxy (,))    = KFun Star (KFun Star Star)
 kindOf (Proxy :: Proxy StateT) = KFun Star (KFun (KFun Star Star) (KFun Star Star))

Just don't try to determine the kind of a polykinded type like Proxy

 kindOf (Proxy :: Proxy Proxy)

which fortunately results in a compiler error in only a finite amount of time.