How does topological sorting of kind variables really work?
Ryan Scott
ryan.gl.scott at gmail.com
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: 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
More information about the ghc-devs
mailing list