Type promotion was introduced in the same paper as kind polymorphism (Giving Haskell a Promotion, by Yorgey et al in 2012). This represented a major leap forward for Haskell's type-level programming capabilities.
Let's explore type promotion in the context of a type-level programming example. We want to create a list where the type itself contains information about the list size.
To represent numbers at type level, we use the age-old Peano numbering which describes the natural numbers (1,2,3, ...) in a recursive manner:
data Zero = Zero
deriving Show
data Succ n = Succ n
deriving Show
one = Succ Zero
two = Succ oneWe'll use this with the understanding that certain bad expressions are still allowed:
badSucc1 = Succ 10 -- :: Succ Int badSucc2 = Succ False -- :: Succ Bool
Our size-aware list type Vec is represented as a GADT:
-- requires
-- {-# LANGUAGE GADTs #-}
-- {-# LANGUAGE KindSignatures #-}
data Vec :: (* -> * -> *) where
Nil :: Vec a Zero
Cons :: a -> Vec a n -> Vec a (Succ n)
nil' = Nil :: Vec Int Zero
cons1 = Cons 3 nil'
-- :: Vec Int (Succ Zero)
cons2 = Cons 5 cons1
-- :: Vec Int (Succ (Succ Zero))The Vec data type has two type parameters: the first represents the list data and the second represents the list size, that is, either Zero or Succ (although this is not enforced by the type-checker).
The Cons data constructor increments the list size as part of the type signature. Every time we cons an element to a list, a different list type is returned, and thereby the list size is incremented. Instead of a size function defined on term-level, we now have a type-level function.
Unfortunately the following is valid:
badVec = Nil :: Vec Zero Zero
However, the following is not valid:
-- badVec2 = Nil :: Vec Zero Bool -- INVALID
We need more type-safety when working with kinds, and for that, we need datatypes on the kind level. That is precisely what the DataKinds extension enables.
The Vec data type expresses type-level programming, but with a very blunt tool, where kinds only describe arity of types and little more.
The DataKinds language extension promotes all (suitable) datatypes to kind level in such a way that we can use the types as kinds in kind signatures. This gives us type-safety at the kind-level. Let's continue with the example from the previous section. First, we unify Zero and Succ into the Nat datatype, as follows:
-- {-# LANGUAGE DataKinds #-}
data Nat = ZeroD | SuccD NatThis gives us more type-safety:
badSuccD = SuccD 10 -- INVALID
The DataKinds language extension will automatically promote the Nat type to the Nat kind. The data-constructors ZeroD and SuccD are promoted to types.
The Vec datatype uses type promotion along with kind polymorphism. The second type parameter is now constrained to be of kind Nat:
data VecD :: * -> Nat -> * where NilD :: VecD a 'ZeroD ConsD :: a -> VecD a n -> VecD a ('SuccD n) cons1D = ConsD 3 NilD -- :: VecD Integer ('SuccD 'ZeroD) cons2D = ConsD '5' NilD -- :: VecD Char ('SuccD 'ZeroD)
Promoted types and kinds can be prefixed with a quote ' to unambiguously specify the promoted type or kind.
The type signature for ConsD uses type 'SuccD (promoted from the datatype constructor SuccD). Similarly, NilD uses the type 'ZeroD.
We created custom kinds by promoting custom datatypes, then we used them to express constrained kind signatures.