Taking HList of Seq[_] and generating Seq[HList] with cartesian product of values

Question

I'm new to Shapless.

I'm trying to write a function that would take an HList of sequences of different types, convert it to a Seq[HList] containing the cartesian product of the original HList's elements, and iterate over the resulting Sequence

For example:

val input = Seq(true, false) :: Seq(1,2,3)::Seq("foo", "bar") :: HNil

cartesianProduct: Seq[Boolean :: Int :: String :: HNil] = Seq(
  true :: 1 :: foo :: HNil, 
  true :: 1 :: bar :: HNil, 
  true :: 2 :: foo :: HNil, 
  true :: 2 :: bar :: HNil, 
  true :: 3 :: foo :: HNil, 
  true :: 3 :: bar :: HNil, 
  false :: 1 :: foo :: HNil, 
  false :: 1 :: bar :: HNil, 
  false :: 2 :: foo :: HNil, 
  false :: 2 :: bar :: HNil, 
  false :: 3 :: foo :: HNil, 
  false :: 3 :: bar :: HNil)

I was able to achieve this in Intellij Scala Worksheet using the following code:

import shapeless._
import shapeless.ops.hlist.LeftFolder


object combine extends Poly {
  implicit def `case`[T <: HList, S] = use((acc : Seq[T], curr : Seq[S]) => {
    for {
      el <- curr
      v <- acc
    } yield el :: v
  })
}

val input = Seq(true, false) :: Seq(1,2,3)::Seq("foo", "bar") :: HNil

val combinations = input.foldLeft(Seq[HNil](HNil))(combine) 

combinations.foreach(println)

Here everything works, I assume, because the full type of input is known to the compiler.

However, when I try to wrap the whole operation in a function, the full type of input gets lost, and I can't call foreach on the result of foldLeft:

def cartesian[T <: HList](input: T)
         (implicit folder: LeftFolder[T, Seq[HNil], combine.type]) = {
  input.foldLeft(Seq[HNil](HNil))(combine)
    .foreach(println)
}

The compiler complains:

  value foreach is not a member of folder.Out
    input.foldLeft(Seq[HNil](HNil))(combine).foreach(println)
                                            ^

I imagine there is some implicit evidence I can request to assert the correct shape of input (HList of Seq[_]) and thus get the compiler to figure out the resulting type of the foldLeft, but I can't figure out what it could be...

Hope someone can help me figure this out. Thanks.

Update: My eventual goal with this question was, given an HList of Seq[_] to derive a function (perhaps on a case class) that will accept a function with the same arg arity as the input HList and the argument types matching the 'Seq' element types in the same order. For example for the input above the function would be f: (Boolean, Int, String) => R So in affect I would be able to iterate over the cartesian product of the input using f. The final code looks like this:

import shapeless._
import shapeless.ops.function.FnToProduct
import shapeless.ops.hlist.LeftFolder
import shapeless.syntax.std.function.fnHListOps


object combine extends Poly {
  implicit def `case`[EL <: HList, S] = use((acc : Seq[EL], curr : Seq[S]) => {
    for {
      el <- curr
      v <- acc
    } yield el :: v
  })
}

case class Cartesian[R <: HList, F, FR](combinations: Seq[R])
                                 (implicit ftp: FnToProduct.Aux[F, R => Unit]) {
  def foreach(f: F) =  combinations.foreach(f.toProduct)
}


def cartesian[T <: HList, R <: HList, F, FR](variants: T)(implicit
                             folder: LeftFolder.Aux[T, Seq[HNil], combine.type, _ <: Seq[R]],
                             fnToProd: FnToProduct.Aux[F, R => Unit]
                            ) = {
  val combinations: Seq[R] = variants.foldLeft(Seq[HNil](HNil))(combine)
  Cartesian(combinations)
}

val variants = Seq(true, false) :: Seq("foo", "bar") :: Seq(1, 2, 3) :: HNil

cartesian(variants).foreach((a, b, c) => println(s"$a, $b, $c"))

Note that the types for the function arguments a, b, c are correctly inferred and are Boolean, String, and Int. Currently the result type of the function passed into foreach has to be fixed (in the code above it is Unit). It can't be inferred from the function passed in.

Sure: import shapeless._ import shapeless.ops.hlist.LeftFolder — dkarlinsky

Oleg Pyzhcov Oleg Pyzhcov · Accepted Answer · 2018-04-21T16:53:50

The problem is not that compiler doesn't know anything about input, but rather that it does not know anything about output.

Inside def cartesian all that is known to compiler is that after foldLeft you get some type folder.Out (which depends on an instance that shapeless would figure for you).

For ensuring result types, you can use LeftFolder.Aux with one extra type parameter, e.g.

def cartesian[T <: HList](input: T)
         (implicit folder: LeftFolder.Aux[T, Seq[HNil], combine.type, _ <: Seq[Any]]) = {
  input.foldLeft(Seq[HNil](HNil))(combine)
    .foreach(println)
}

Now the compiler will know that result is some subtype of Seq[Any], so it is possible to call foreach on it.

Of course, this is only the problem inside the def. At call sites output types will be resolved based on input, so you would be able to do this without Aux:

def cartesian2[T <: HList](input: T)
         (implicit folder: LeftFolder[T, Seq[HNil], combine.type]) = {
  input.foldLeft(Seq[HNil](HNil))(combine)
}

cartesian2(input).foreach(println)

Runnable code: https://scalafiddle.io/sf/n409yNW/2

Taking HList of Seq[_] and generating Seq[HList] with cartesian product of values

1 Answers