How does topological sorting of kind variables really work?

Ryan Scott at
Tue Apr 12 23:47:13 UTC 2016

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
      :: 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.

More information about the ghc-devs mailing list