Chapter 7. Patterns of Kind Abstraction

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 data­types (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:

  • Higher-order kinds
  • Higher-kinded polymorphism
  • Associated type synonyms
  • Type (synonym) families
  • Kind polymorphism
  • Type promotion
  • Type-level programming
  • Dependently-typed programming

Higher-order kinds

Types classify values at different levels of abstraction, for example:

­­-- Primitive types 
­­-- "a string"   :: String 
­­-- 12             :: Int  
 
--­­ instances of higher­order, parametrized types 
­­-- Just 10      :: Maybe Int 
­­-- Left 10      :: Either Int b 
 
­­-- functions are first class values 
­­-- (* 2)          :: Num a => a ­> a 
 
­­-- type­constructors 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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset