Haskell Polymorphism With Kinds and Type Variables

Question

In Haskell I have learnt that there are type variables (ex. id :: a -> a), applied to type signatures, and kinds (ex. Maybe :: * -> *), applied to type constructors and type classes. A type must have kind * (be a concrete type) in order to hold values.

We use type variables to enable polymorphism: Nothing :: Maybe a means that the constant Nothing can belong to a family of possible types. This leads me to believe that kinding and type variables serve the same purpose; wouldn't the last code sample work as simply Nothing :: Maybe, where type class Maybe remains with the kind * -> * to signify that the type belongs to generic family?

What it seems we are doing is taking an empty parameter (* -> *) and filling it in with a type variable (a) that represents the same level of variance.

We see this behavior in another example:

>>> :k Either
Either :: * -> * -> *
>>> :t Left ()
Left () :: Either () b
>>> :t Right ()
Right () :: Either a ()

Why is it theoretically necessary to make the distinction between kinds and type variables?

@bheklilr I think OP has something different in mind, although I don't quite get it. — András Kovács
– András Kovács, Commented Aug 24, 2016 at 18:44
If you enable PartialTypeSignatures, you can put _ instead of type variables. For example, Nothing :: Maybe _ or Left () :: Either _ _. What you propose would be a simple syntactic extension, but I'm not sure it wouldn't introduce more confusion (especially in the context of other extensions like PolyKinds) — Alec
– Alec, Commented Aug 24, 2016 at 18:47

Alexey Romanov · Accepted Answer · 2016-08-24 19:17:52Z

5

They are distinct just like typing and usual (value-level) variables are distinct. Variables have types, but they aren't types. So also, type variables have kinds. Type variables are the primary notion: without them you don't have parametric polymorphism, and they exist also in many other languages like Java, C#, etc. But Haskell goes further in allowing types-which-take-parameters ([], Maybe, ->, etc.) to exist on their own and to have type variables which represent such non-concrete types. And this means it needs a kind system to disallow things like Maybe Int Int.

From the example, it seems that you suggest that you can write a signature without type variables and restore it to the signature with them. But then how could you distinguish a -> b -> a and a -> b -> b?

edited Aug 24, 2016 at 19:17

answered Aug 24, 2016 at 19:08

Alexey Romanov

172k38 gold badges329 silver badges509 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

augustss Over a year ago

It's fine to mash types and kinds together. In fact, the latest ghc has a language extension for that. Though, viewed as a logic type-in-type has to be handled very carefully to avoid inconsistencies. But that doesn't matter for Haskell.

Collectives™ on Stack Overflow

Haskell Polymorphism With Kinds and Type Variables

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related