wiki:KindInference

Version 3 (modified by ross@…, 8 years ago) (diff)

--

Kind Inference

Ticket(s)

Brief Explanation

Haskell 98 lacks kind polymorphism, and performs kind inference over dependency groups with polymorphic kinds defaulted to *. The Report gives the following example of illegal declarations:

data Tree a = Leaf | Fork (Tree a) (Tree a)

type TreeList = Tree []     -- illegal

(because Tree has been assigned the kind * -> *).

A more meaningful example is the following attempt to compose monad transformers:

newtype StateT s m a = S (s -> m (a,s))

newtype ReaderT r m a = R (r -> m a)

newtype Compose f g m a = C (f (g m) a)

type SR s r = Compose (StateT s) (ReaderT r)     -- illegal

GHC users have been able to work around this by adding KindAnnotations to the above definition of Compose.

References

Alternatives

Listed in order of decreasing need for KindAnnotations (even if you think those are useful in their own right):

GHC 6.4

Kind inference is performed across all the data, newtype, type and class declarations of a module before defaulting, and so the above examples are accepted.

Monomorphic kinds, using all available information

Kind inference is performed across the whole module, using all occurrences of type constructors and classes, i.e. the above sources plus instance declarations, type signature declarations and expression type signatures.

Polymorphic kinds

Type constructors and classes have polymorphic kinds, inferred over dependency groups. KindAnnotations would never be required.