How does topological sorting of kind variables really work?

Ryan Scott at
Wed Apr 13 02:44:29 UTC 2016

Aha! For some reason, it never clicked that you could use forall
within a datatype's kind signature like that. That technique would, at
the very least, allow me to guarantee the order in which the kind
variables appear. Thanks!

It's a bit of a shame that type inference doesn't give you a reliable
order, but I suppose if you rely on -XTypeApplications working a
certain way, you're taking a risk by NOT using a forall.

Ryan S.

On Tue, Apr 12, 2016 at 10:30 PM, Richard Eisenberg <eir at> wrote:
> I don't think this has to do with topological sorting so much as inferring the order of undeclared (but written) kind variables. You could, with -XTypeInType, always make the order explicit:
>> data T :: forall j k l x y z. (j -> k -> l) -> (x, y, z) -> * where MkT :: T a b
> The order of these variables is derived from the extractHsTyRdrTyVars function and friends in RnTypes. I'm sure you could look closely at those functions and see where the behavior is coming from. It's very likely an improvement can be found here.
> Richard
> On Apr 12, 2016, at 7:47 PM, Ryan Scott < at> wrote:
>> I'm doing some work in GHC that requires explicitly applying kinds to
>> the kind variables of a data type. I noticed that the order in which
>> the implicit kind variables are sorted is not as predictable as I
>> originally thought. To illustrate what I mean, here is a GHCi session
>> I had recently (with GHC HEAD):
>>    $ /opt/ghc/head/bin/ghci -XTypeInType
>>    GHCi, version 8.1.20160412:  :? for help
>>    Loaded GHCi configuration from /home/ryanglscott/.ghci
>>> data T (a :: j -> k -> l) (b :: (x, y, z)) = MkT
>>> :t MkT
>>    MkT
>>      :: forall x y z l k j (a :: j -> k -> l) (b :: (x, y, z)). T a b
>> Much to my surprise, the order of the kind variables wasn't [j, k, l,
>> x, y, z], but rather [x, y, z, l, k, j]! I know that type variables
>> are sorted with a stable topological sort [1], but there must be some
>> other subtlety that I'm missing. How does GHC come up with the order
>> [x, y, z, l, k, j]?
>> Ryan S.
>> -----
>> [1]
>> _______________________________________________
>> ghc-devs mailing list
>> ghc-devs at

More information about the ghc-devs mailing list