Type families bring functions to the type-level. Polymorphic kinds bring polymorphism to the kind-level. Type promotion bring datatypes and type-safety to the kind-level.
Two major problems of the Haskell kind system are solved by these extensions:
- The kind system is too restrictive (because it lacks polymorphism)
- Solution: Provide polymorphism on the kind level
(PolyKinds)
- Solution: Provide polymorphism on the kind level
- The kind system is too permissive (kinds are too vague)
- Solution: Promote datatypes to kinds to simulate a type-system on the kind-level
(DataKinds)
- Solution: Promote datatypes to kinds to simulate a type-system on the kind-level
Haskell98 already carried the seed for type-level programming by including multiparameter type-classes. Since then, the Haskell kind-system has been enriched with functional dependencies, GADTs, type families, kind polymorphism, and type-promotion.
Together, these extensions provide the building blocks for type-level programming in Haskell.
Returning to our earlier example, let's write a type-level function that computes type-level numbers. Since we have lists with types that encode their size, we can write an append function that encodes the appended list size in the return type:
vappend :: VecD e n -> VecD e m -> VecD e (Add n m)
vappend NilD l = l
vappend (ConsD x xs) ys = ConsD x (vappend xs ys)
Add is a type level function that adds two type-level numbers. We can express this as a type family:
type family Add (n :: Nat) (m :: Nat) :: NatThe kind signature constrains the types in an analogous way to regular type signatures constraining terms. Instances of the family use pattern matching on types instead of pattern matching on data-constructors:
type instance Add ZeroD m = m type instance Add (SuccD n) m = SuccD (Add n m)
Let's append two Vec data types:
xs = vappend (ConsD 3 (ConsD 5 NilD))
(ConsD 7 NilD)
-- xs :: VecD Integer ('SuccD ('SuccD ('SuccD 'ZeroD)))The Add type-function calculates the combined vector size and demonstrates the humble beginnings of typelevel arithmetic (arithmetic that is executed during the typechecking phase). This is a well explored topic in the Haskell community (https://wiki.haskell.org/Type_arithmetic).
At this point in our discussion, type-level programming still lacks the expressiveness of term-level programming. In particular, we don't have these language features on type-level: case expressions, anonymous functions, partially applied functions, and let expressions.
This changed in 2014 when these features were added to typelevel using template programming techniques (see Promoting functions to type families in Haskell by Eisenberg and Stolarek). The singletons library (https://hackage.haskell.org/package/singletons) flowed out of this work.
These extensions of the kindsystem enable us to write ever more sophisticated code at the termlevel and then automatically promote the code to typelevel. Put another way, we can write code that operates at both term and type levels.
By further extending the type-level in these ways, we can write (more and more) code at term-level that can automatically be promoted to type-level. Put another way, we can write code that operates at both term and type levels.
In 2014, the type-family picture was completed (for now) with the addition of closed type families, where all instances of the type family are declared in one place. This restriction brings the benefit of type-inference, which is lost with open type families (refer to Promoting Functions to Type Families, 2014, Eisenberg et al):
-- {-# LANGUAGE TypeFamilies #-}
-- closed-type family
type family IsZero (n::Nat) :: Bool where
IsZero 'ZeroD = 'True
IsZero ('SuccD n) = 'False
IsZero is a type-level function that matches pattern against types.
The following table shows a timeline of the key advances of the Haskell kind-system:
|
Year |
Language extension |
Advance in Type-level programming |
|---|---|---|
|
1997 |
MultiParamTypeClasses |
Basis for Type functions |
|
2000 |
FunctionalDependencies |
Type-level functions (relational-style) |
|
2003 |
GADTs |
Type refinement |
|
2005 |
TypeFamilies — Associated Types |
Type-level functions, type-class bound |
|
2008 |
TypeFamilies — top-level and associated types unified |
Type-level functions, top level and type-class bound |
|
2012 |
PolyKinds — Kind polymorphism |
Type-level polymorphism |
|
2012 |
DataKinds — Type Promotion |
Type-level datatypes, type-safety |
|
2014 |
TypeFamilies — Closed-type families |
Type families with type-inference |
|
2014 |
Singletons library |
Type-level: case, let, lambdas, currying |
Type-level programming can be considered to be another pattern of generic programming. Furthermore, it interacts with two other types of generic programming:
- As we saw in the examples of this chapter, type-level programming techniques are useful in implementing datatype generic programming. Also, there are some generic programs that can be written at type-level instead of term-level.
- We also saw that template metaprogramming is used in type-level programming and datatype generic programming.
While template metaprogramming, datatype generic programming, and type-level programming all happen at different levels of abstraction and different phases of program execution, they also weave together and push each other forward.