Type Level Heterogeneous List

June 20, 2017
haskell

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.

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

References