HNil

HNil is a term used in programming languages and libraries that implement heterogeneously typed lists, commonly known as HLists. It represents the empty HList and serves as the terminator for a sequence of elements with potentially different types. The existence of HNil allows the type system to encode both the length of the list and the exact types of its elements.

In practice, HNil is the base case in the inductive definition of an HList. An HList is built by repeatedly prepending elements of various types to a tail HList, typically using a constructor like HCons or the :: operator, until the tail becomes HNil. For example, in Scala’s shapeless library one can construct an HList such as 1 :: "two" :: HNil, which has the type Int :: String :: HNil. The value HNil represents the empty end of the list, and the type of the entire structure encodes the sequence of element types.

From a type-theoretic perspective, HNil provides a uniform terminator for recursive operations on HLists, enabling type-safe implementations of functions like map, fold, zip, and reverse. Pattern matching or type-class based dispatch commonly recognizes HNil as the end case, analogous to the empty list in homogeneous lists but with the added complexity of varying element types.

Different ecosystems may treat HNil slightly differently. In some languages (such as Haskell), HNil is a data constructor, while in others (like Scala with shapeless) it is an object that marks the end of an HList. Regardless of syntax, HNil is central to enabling statically typed, heterogeneous collections.

See also: HList, HCons, shapeless, Haskell HList, type-level programming.