Creating an HList of all pairs from two HLists

Question

I'm using shapeless in Scala, and I'd like to write a function allPairs that will take two HLists and return an HList of all pairs of elements. For example:

import shapeless._
val list1 = 1 :: "one" :: HNil
val list2 = 2 :: "two" :: HNil
// Has value (1, 2) :: (1, "two") :: ("one", 2) :: ("one", "two") :: HNil
val list3 = allPairs(list1, list2)

Any idea how to do this?

Also, I'd like to emphasize I'm looking for a function, not an inlined block of code.

Answer 1

You can't use a for-comprehension or a combination of map and flatMap with function literals here (as the other answers suggest), since these methods on HList require higher rank functions. If you just have two statically typed lists, this is easy:

import shapeless._

val xs = 1 :: 'b :: 'c' :: HNil
val ys = 4.0 :: "e" :: HNil

object eachFirst extends Poly1 {
  implicit def default[A] = at[A] { a =>
    object second extends Poly1 { implicit def default[B] = at[B](a -> _) }
    ys map second
  }
}

val cartesianProductXsYs = xs flatMap eachFirst

Which gives us the following (appropriately typed):

(1,4.0) :: (1,e) :: ('b,4.0) :: ('b,e) :: (c,4.0) :: (c,e) :: HNil

Writing a method that will do this with HList arguments is trickier. Here's a quick example of how it can be done (with some slightly more general machinery).

I'll start by noting that we can think of finding the Cartesian product of two ordinary lists as "lifting" a function that takes two arguments and returns them as a tuple into the applicative functor for lists. For example, you can write the following in Haskell:

import Control.Applicative (liftA2)

cartesianProd :: [a] -> [b] -> [(a, b)]
cartesianProd = liftA2 (,)

We can write a polymorphic binary function that corresponds to (,) here:

import shapeless._

object tuple extends Poly2 {
  implicit def whatever[A, B] = at[A, B] { case (a, b) => (a, b) }
}

And define our example lists again for completeness:

val xs = 1 :: 'b :: 'c' :: HNil
val ys = 4.0 :: "e" :: HNil

Now we'll work toward a method named liftA2 that will allow us to write the following:

liftA2(tuple)(xs, ys)

And get the correct result. The name liftA2 is a little misleading, since we don't really have an applicative functor instance, and since it's not generic—I'm working on the model of the methods named flatMap and map on HList, and am open to suggestions for something better.

Now we need a type class that will allow us to take a Poly2, partially apply it to something, and map the resulting unary function over an HList:

trait ApplyMapper[HF, A, X <: HList, Out <: HList] {
  def apply(a: A, x: X): Out
}

object ApplyMapper {
  implicit def hnil[HF, A] = new ApplyMapper[HF, A, HNil, HNil] {
    def apply(a: A, x: HNil) = HNil
  }
  implicit def hlist[HF, A, XH, XT <: HList, OutH, OutT <: HList](implicit
    pb: Poly.Pullback2Aux[HF, A, XH, OutH],
    am: ApplyMapper[HF, A, XT, OutT]
  ) = new ApplyMapper[HF, A, XH :: XT, OutH :: OutT] {
    def apply(a: A, x: XH :: XT) = pb(a, x.head) :: am(a, x.tail)
  }
}

And now a type class to help with the lifting:

trait LiftA2[HF, X <: HList, Y <: HList, Out <: HList] {
  def apply(x: X, y: Y): Out
}

object LiftA2 {
  implicit def hnil[HF, Y <: HList] = new LiftA2[HF, HNil, Y, HNil] {
    def apply(x: HNil, y: Y) = HNil
  }

  implicit def hlist[
    HF, XH, XT <: HList, Y <: HList,
    Out1 <: HList, Out2 <: HList, Out <: HList
  ](implicit
    am: ApplyMapper[HF, XH, Y, Out1],
    lift: LiftA2[HF, XT, Y, Out2],
    prepend : PrependAux[Out1, Out2, Out]
  ) = new LiftA2[HF, XH :: XT, Y, Out] {
    def apply(x: XH :: XT, y: Y) = prepend(am(x.head, y), lift(x.tail, y))
  }
}

And finally our method itself:

def liftA2[HF, X <: HList, Y <: HList, Out <: HList](hf: HF)(x: X, y: Y)(implicit
  lift: LiftA2[HF, X, Y, Out]
) = lift(x, y)

And that's all—now liftA2(tuple)(xs, ys) works.

scala> type Result =
     |   (Int, Double) :: (Int, String) ::
     |   (Symbol, Double) :: (Symbol, String) ::
     |   (Char, Double) :: (Char, String) :: HNil
defined type alias Result

scala> val res: Result = liftA2(tuple)(xs, ys)
res: Result = (1,4.0) :: (1,e) :: ('b,4.0) :: ('b,e) :: (c,4.0) :: (c,e) :: HNil

Just as we wanted.