A better "add" operator for HLists

At Haskell eXchange 2019, Yves Parès was presenting his “porcupine” library, a library to help scientists run data pipelines using the power of Haskell’s arrows. At some stage, he said, “you know if you’re using a ‘records’ library, like Vinyl, you have to build your HList by appending RNil at the end”. And I thought: No!

This is a very small thing that has been bugging me for some time. If I want to build a HList, why do I have to append HNil at the end? As soon as I’m appending 2 things together to form an HList the whole type should be determined, isn’t it? Let’s work on a bit of code.

Here is the standard definition of a HList in Haskell:

data HList (l::[*]) where
  HNil  :: HList '[]
  HCons :: e -> HList l -> HList (e ': l)

-- example
myHList :: HList [Int, Text]
myHList = HCons 1 (HCons "Hello" HNil)

I can define a :+ operator to make the operation of appending an element a bit nicer:

infixr 5 +:
(+:) :: a -> HList as -> HList (a : as)
(+:) = HCons

myHList1 :: HList [Int, Text]
myHList1 =
     1
  +: "Hello"
  +: HNil

I can also define an <+> operator to append 2 HLists together:

-- :++ is a type-level operator (not defined here)
-- for appending 2 lists of types together (see the Appendix)

infixr 4 <+>
(<+>) :: HList as -> HList bs -> HList (as :++ bs)
(<+>) HNil bs = bs
(<+>) (HCons a as) bs = HCons a (as <+> bs)

list1 :: HList [Int, Text]
list1 = 1 +: "Hello" +: HNil

list2 :: HList [Double, Bool]
list2 = 2.0 +: True +: HNil

lists :: HList [Int, Text, Double, Bool]
lists = list1 <+> list2

All good so far, that’s a reasonable API. However we still need to specify HNil every time we create a new HList. Can we avoid it?

A more polymorphic operator

In order to avoid using HNil we need to have an operator, let’s call it <:, to know what to do when:

• adding one element to another: a <: b
• adding one element to a HList: a <: bs

But even better we should be able to:

• append 2 HList together: as <: bs
• append an element at the end of a HList: as <: b

We can already see that this operator can not be a straightforward Haskell functions, because the types of its first and second arguments are not always the same. Annoying. Wait, there’s a tool in Haskell to cope with variations in types like that: typeclasses!

infixr 5 <:
class AddLike a b c | a b -> c where
  (<:) :: a -> b -> c

instance {-# OVERLAPPING #-} (asbs ~ (as :++ bs)) =>
  AddLike (HList as) (HList bs) (HList asbs) where
  (<:) = (<+>)

instance (abs ~ (a : bs)) => AddLike a (HList bs) (HList abs) where
  (<:) = (+:)

instance AddLike a b (HList [a, b]) where
  (<:) a b = a +: b +: HNil

instance (asb ~ (as :++ '[b])) => AddLike (HList as) b (HList asb) where
  as <: b = as <+> (b +: HNil)

This AddLike typeclass will deal with all the cases and now we can write:

a = 1 :: Int
b = "hello" :: Text
c = 2.0 :: Double
d = True :: Bool

ab = a <: b
bc = b <: c

abc = a <: bc
bca = bc <: a

abcd = ad <: cd

That’s it, one operator for all the reasonable cases.

Appendix

Here is the full code:

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE UndecidableInstances #-}
{-# LANGUAGE PolyKinds #-}
{-# OPTIONS_GHC -fno-warn-unticked-promoted-constructors #-}

module AddLikeApi where

import Protolude

data HList (l :: [Type]) where
  HNil  :: HList '[]
  HCons :: e -> HList l -> HList (e ': l)

myHList :: HList [Int, Text]
myHList = HCons 1 (HCons "Hello" HNil)

infixr 5 +:
(+:) :: a -> HList as -> HList (a : as)
(+:) = HCons

myHList' :: HList [Int, Text]
myHList' =
     1
  +: "Hello"
  +: HNil

-- * Appendix

infixr 4 <+>
(<+>) :: HList as -> HList bs -> HList (as :++ bs)
(<+>) HNil bs = bs
(<+>) (HCons a as) bs = HCons a (as <+> bs)

infixr 5 <:
class AddLike a b c | a b -> c where
  (<:) :: a -> b -> c

instance {-# OVERLAPPING #-} (asbs ~ (as :++ bs)) => 
  AddLike (HList as) (HList bs) (HList asbs) where
  (<:) = (<+>)

instance (abs ~ (a : bs)) => AddLike a (HList bs) (HList abs) where
  (<:) = (+:)

instance AddLike a b (HList [a, b]) where
  (<:) a b = a +: b +: HNil

instance (asb ~ (as :++ '[b])) => AddLike (HList as) b (HList asb) where
  as <: b = as <+> (b +: HNil)

type family (:++) (x :: [k]) (y :: [k]) :: [k] where
  '[]      :++ xs = xs
  (x : xs) :++ ys = x : (xs :++ ys)

-- examples
list1 :: HList [Int, Text]
list1 = 1 +: "Hello" +: HNil

list2 :: HList [Double, Bool]
list2 = 2.0 +: True +: HNil

lists :: HList [Int, Text, Double, Bool]
lists = list1 <+> list2

a = 1 :: Int
b = "hello" :: Text
c = 2.0 :: Double
d = True :: Bool

ab :: HList [Int, Text]
ab = a <: b

bc :: HList [Text, Double]
bc = b <: c

cd :: HList [Double, Bool]
cd = c <: d

abc' :: HList [Int, Text, Double]
abc' = ab <: c

abc :: HList [Int, Text, Double]
abc = a <: bc

abcd :: HList [Int, Text, Double, Bool]
abcd = ab <: cd