Kind polymorphism

Type families gives us functions at the type-level (through type functions). Analogously, the Polykinds language extension gives us polymorphism at the type-level.

Kind polymorphism (Giving Haskell a Promotion, by Yorgey et al in 2012) allows us to describe more generic data and functions. For example, when designing a type-class, the need may arise to cater for various kind-orders. Consider the multiple Typeable classes for multiple arities as an example:

class Typeable (a :: * ) where
  typeOf :: a -> TypeRep

class Typeable1 (a :: * -> *) where
  typeOf1 :: forall b. a b -> TypeRep

The same goes for the Generic type-class we encountered earlier: we need to define different type-classes for different kind arities.

To explore kind polymorphism, we'll work with a trivialized version of Typeable, where the typeOf function simply returns a string instead of a TypeRep:

class T0 a where
  f0 :: a -> String

instance T0 Int where
  f0 _ = "T0 Int"

instance T0 Char where
  f0 _ = "T0 Char"

The function f0 gives us the type as a string for each Int or Char value:

-- f0 (10::Int)
--   "T0 Int"
-- f0 'x'
--   "T0 Char"

We can involve higher-kinded types as instances, such as Maybe:

  instance T0 (Maybe a) where
    f0 _  = "T0 Maybe a"

However, we have to specify parameter a for Maybe :: * -> * to match the required kind * of T0. We cannot define instance T0 Maybe, for that we need to create another type-class to deal with the higher-kinded case:

class T1 m where -- m :: * -> *
  f1 :: Show a => m a -> String

instance T1 Maybe where
  f1 _ = "T1 Maybe"

The type­class T1 can deal with the higher­-kinded case but not the monomorphic case:

-- f1 (Just 10)
--   "T1 Maybe"

-- but not
--  instance T1 Int where
--    f1 _ = "T1 Int"

Polymorphic kinds allow us to unify these type-classes into one.

The PolyKinds language extension

A kind-polymorphic type-class looks quite normal at first glance:

-- {-# LANGUAGE PolyKinds #-}
class T a where -- (a::k)
  f :: Proxy a -> String

Type a has kind parameter k. With the PolyKinds language extension, k is polymorphic by default, that is, k can take several forms (of kind signatures):

  class T a where
  -- (a::k)

  -- *
  -- * -> *
  -- * -> * -> *

The parameter k is a polymorphic placeholder for many possible kind arities.

The Proxy type is a kind-polymorphic phantom-type:

  data Proxy a = Proxy -– (a::k)
    deriving Show

The type parameter a has polymorphic kind, for example:

  (Proxy Int)    -- Proxy :: *        -> *
  (Proxy Maybe)  -- Proxy :: (* -> *) -> *

Proxy is used to generalize the kind of the function argument, for example:

  f :: T a => Proxy a -> String -- types
  --    k  =>   k     -> *      -- kinds

The first argument of f can take a type with any kind-order (arity). Note that the type a in Proxy a is constrained by the type-class T a, which is also kind polymorphic in the type a.

If we interrogate the kinds before and after the PolyKinds language extension (for example, ghci> :k f gives the kind signature of f), we can see how the kind signatures are generalized by PolyKinds:

  -- kind signatures: before and after PolyKinds

  -- before
  f  :: *              -> *
  -- after
  f  :: forall k. k    -> *

  -- before
  Proxy :: *           -> *
  -- after
  Proxy :: forall k. k -> *

Note how the first argument of f is kind-polymorphic (thanks to the kind-polymorphic phantom type Proxy).

The forall keyword makes an appearance on the type-level in a way similar to how it is used with RankN types to describe nested function polymorphism. We can verify that the type parameter has polymorphic kind:

  instance T Int where -- Int :: *
    f _ = "T Int"

  instance T Maybe where -- Maybe :: * -> *
    f _  = "T Maybe"

  -- f (Proxy :: Proxy Maybe) -- "T Maybe"
  -- f (Proxy :: Proxy Int)   -- "T Int"

The particular type of Proxy we pass to f determines the type-class at which the function will be invoked. In this example, kind-polymorphism appears in three different guises:

  • T is a kind-polymorphic type-class
  • The Proxy datatype is kind-polymorphic (it takes types of any kind-order and returns a * kind)
  • The Proxy data-constructor is a kind-polymorphic function

Regular polymorphism over functions and types increases the opportunities for abstraction. The same is true for kind polymorphism at the type level.

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

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