Implementing type-safe heterogeneous collections

[blamario]

@brandonchinn178

@blamario

an HList is not actually a list but a bunch of nested pairs

Can you elaborate? That doesn’t make sense to me. The canonical HList I’m familiar with is

data HList xs where
  Nil :: HList []
  (:&) :: x -> HList xs -> HList (x : xs)

foo :: HList [Int, Bool]
foo = 1 :& True :& Nil

…

Sure, that looks much like a regular list definition, but it’s isomorphic to – and has exactly the same memory layout as – this definition:

type family HList2 (xs :: [Type]) where
  HList2 '[] = ()
  HList2 (x ': xs) = (x, HList2 xs)

foo :: HList2 [Int, Bool]
foo = (1, (True, ()))

You might object that the regular list datatype can also be represented as nested pairs and you’d be right, but the regular list has a single parameter type and that makes a world of difference in what you can do with it. It makes no sense to speak of an infinite HList for example, because its type would also be infinite and GHC wouldn’t allow it.