Type-level programming involves computation at type-level that is executed during the type-checking phase.
In earlier chapters, we saw the beginnings of type-level programming when we used functional dependencies and GADTs, but to do proper type-level programming, we need an even more enriched Kind-system.
We will freely interchange the terms type-level and kind-level, since in Haskell, type-level programming happens at the level of kinds.
Type-level programming stands in contrast to term-level programming, in that the former executes in the type-checking phase and the latter executes at runtime.
In this chapter, we will explore patterns of kind-abstraction as they relate to type-level programming. First, we will look at the basic Kindsystem, extend it with associated types, and then look at more generalized type
families.
In the last round of extensions, we will add polymorphism and datatypes (via data type promotion) to the Kind-system. Together, these extensions form the basis for type-level programming in Haskell.
We finish the chapter and the book at the very edge of Haskell when we look into Dependently-typed programming.
In this chapter, we will cover the following topics:
Types classify values at different levels of abstraction, for example:
-- Primitive types -- "a string" :: String -- 12 :: Int -- instances of higherorder, parametrized types -- Just 10 :: Maybe Int -- Left 10 :: Either Int b -- functions are first class values -- (* 2) :: Num a => a > a -- typeconstructors are functions -- Just :: a > Maybe a -- Left :: a > Either a b
In a similar way, kinds classify types. For monomorphic types (that is, not polymorphic), the kind signature is just the placeholder *
:
-- TYPE KIND -- [Char] :: * -- Maybe Int :: *
Parametric types express higher-order kinds, for example:
Maybe :: * -> * -- a -> Maybe a
where (* -> *)
is a placeholder for a -> Maybe a
. Let's compare this with the kind signature of Either
:
-- Either * -> * -> * -- a -> b -> Either a b
The Haskell kind system can distinguish between two main kinds: lifted types (of kind *
) and type constructors (for example, * -> * -> *
).
Kind signatures signify the arity of parameterization of a type, that is, the number and position of type parameters in a type. However, arity says nothing about type; the Haskell kind system is untyped.