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.

Polyphyletic

Precisely what distinction do you draw between a "function" and "an inlined block of code?" – Foghorn

@RandallSchulz: See the difference between Travis' first answer below and his final answer using liftA2. – Polyphyletic

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.

Lightner

This is nice. Could you show how you would pack this into a method taking xs and ys as parameters? I tried to do it this way and badly failed. – Shavian

@RégisJean-Gilles: That's a good question—it turns out that you will need some more machinery to generalize this to a method. I'm taking a stab at it now. – Lightner

The question asks for a function; I think that's the hard part. – Polyphyletic

@emchristiansen: Right—see this tweet and Miles Sabin's response. I started working on it on my way out the door this morning, and will update this evening (unless someone else gets it first). – Lightner

@TravisBrown: Impressive. Thank you. – Polyphyletic

Nice work. I wish I could upvote once more. Then again, I'm not sure I should be thrilled to see how complex the result is. The joys and pains of metaprogramming I guess. BTW is there any documentation for shapeless somewhere? Part of the difficulty when trying to solve the puzzle was reverse-engineering the purpose of Pullback1Aux, Case1, Case2, and all the funny animals that live in the shapeless zoo. – Shavian

Well, you could shave a few lines off the top if you didn't need the generic version, and you could probably clean it up a bit otherwise, but yeah, this is more or less abuse of the type system, and isn't going to get a lot cleaner. – Lightner