How does topological sorting of kind variables really work?

[Richard Eisenberg]

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 <ryan.gl.scott at gmail.com> 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: http://www.haskell.org/ghc/  :? 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] http://git.haskell.org/ghc.git/blob/d81cdc227cd487659995ddea577214314c9b4b97:/docs/users_guide/glasgow_exts.rst#l8708
> _______________________________________________
> ghc-devs mailing list
> ghc-devs at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs