Type-Level Heterogeneous List

2017-06-20

HList is a well designed package for type level heterogeneous lists. We will take a look at the main declaration to get more familiar with type level programmin in Haskell. If you are new to kinds in Haskell, start with Kinds in Haskell and An Introduction to Type Families. Then Type-Level List Search.

Promote data types to to kind level. We want to use [] at the type level to operate over a list of types that we use to calculate the type signature.

{-# LANGUAGE DataKinds          #-}

Allow multiparameter typeclass instances instance C (Either a String) where ....

{-# LANGUAGE FlexibleContexts   #-}

Allow typeclass instances for nested types instance C (Maybe Int) where ....

{-# LANGUAGE FlexibleInstances  #-}

Allow deriving instance separated from the type declaration. It can be in the same file or another file.

{-# LANGUAGE StandaloneDeriving #-}

Allow indexed and data type families. The instances of data families can be data types and newtypes.

{-# LANGUAGE TypeFamilies       #-}

Allow the use and definition of types with operator names.

{-# LANGUAGE TypeOperators      #-}

HList is a list of inhabited types. They must be of kind *. HNil is an empty list of types. HCons is a constructor to concatentate to types.

data family HList (l :: [*])
data instance HList '[] = HNil
data instance HList (x ': xs) = x `HCons` HList xs

With deriving instance, Eq and Ord are straightforward.

deriving instance Eq (HList '[])
deriving instance (Eq x, Eq (HList xs)) => Eq (HList (x ': xs))

deriving instance Ord (HList '[])
deriving instance (Ord x, Ord (HList xs)) => Ord (HList (x ': xs))

Finally, we can iterate over the types to create an instance of Show and run a simple example.

instance Show (HList '[]) where
  show _ = "H[]"

instance (Show e, Show (HList l)) => Show (HList (e ': l)) where
  show (HCons x l) = 
    let 'H':'[':s = show l
    in "H[" ++ show x ++
         (if s == "]" then s else "," ++ s)
         
infixr 2 `HCons`

foo :: HList '[Char, String, Double]
foo = 'Z' `HCons` "Zebra" `HCons` 2.5 `HCons` HNil

main :: IO ()
main = print foo

Type-Level Heterogeneous List

References