shapeless filter a list of options

I am new to shapeless and try to tackle the following problem. I have tuples of different length with Option[(R[A], A)] as elements and would like to kind of filter the tuple so that it results only in Some. Notice that I don't have Some or None at compile time but only Option. I think I have kind of a recursive problem but cannot describe it. I have something like the following in mind (where I have already converted the tuple into an HList:

def performFinalStep[A1](t: Tuple1[A1]) = ???
def performFinalStep[A1, A2](t: Tuple2[A1, A2]) = ???
...

def reduce[T <: HList, A <: HList](l: Option[(R[A], A)] :: T, acc: A) = {
  case h :: HNil => performFinalStep(toTuple(h :: acc))
  case h :: t => reduce(t, h :: acc) //does not work as it is not known if T's head is Option[(R[A], A)]
}

reduce((Option(R(1), 2), Option(R("S", "s"))).productElements, HNil)

There are two things I don't know, how do I turn an HList back into a tuple and how can I overcome the typing for T?

Solution

In Shapeless converting case classes to HLists and vice versa can be done via shapeless.Generic. And in Scala Tuples are case classes. But there is standard way

(1 :: "a" :: true :: HNil).tupled // (1,a,true)

import shapeless.ops.hlist.Tupler
def toTuple[L <: HList](l : L)(implicit tupler: Tupler[L]): tupler.Out = l.tupled

When you can't express something with a method you create a type class (I don't know your actual type instead of Nothing)

case class R[A](a: A)

trait Reduce[L <: HList, Acc <: HList] {
  def apply(l: L, acc: Acc): Nothing
}

object Reduce {
  implicit def singletonCase[A, Acc <: HList](implicit
    tupler: Tupler[Option[(R[A], A)] :: Acc]): Reduce[Option[(R[A], A)] :: HNil, Acc] =
    (l, acc) => l match {
      case h :: HNil => performFinalStep(toTuple(h :: acc))
    }

  implicit def notSingletonCase[H, T <: HList, Acc <: HList](implicit
    reduce: Reduce[T, H :: Acc]): Reduce[H :: T, Acc] =
    (l, acc) => l match {
      case h :: t => reduce(t, h :: acc)
    }
}

def reduce[L <: HList, Acc <: HList](l: L, acc: Acc)(implicit 
  r: Reduce[L, Acc]): Nothing  = r(l, acc)

Next trouble is

Error:(39, 27) overloaded method value performFinalStep with alternatives:
  [A1, A2](t: (A1, A2))Nothing <and>
  [A1](t: (A1,))Nothing
 cannot be applied to (tupler.Out)
        case h :: HNil => performFinalStep(toTuple(h :: acc))

You can try one more type class

trait PerformFinalStep[P <: Product] {
  def apply(t: P): Nothing
}

object PerformFinalStep {
  implicit def tuple1[A1]: PerformFinalStep[Tuple1[A1]] = t => ???
  implicit def tuple2[A1, A2]: PerformFinalStep[Tuple2[A1, A2]] = t => ???
  // ...
}

def performFinalStep[T <: Product](t: T)(implicit 
  pfs: PerformFinalStep[T]) = pfs(t)

trait Reduce[L <: HList, Acc <: HList] {
  def apply(l: L, acc: Acc): Nothing
}

object Reduce {
  implicit def singletonCase[A, Acc <: HList, P <: Product](implicit
    tupler: Tupler.Aux[Option[(R[A], A)] :: Acc, P],
    pfs: PerformFinalStep[P]): Reduce[Option[(R[A], A)] :: HNil, Acc] =
    (l, acc) => l match {
      case h :: HNil => performFinalStep(toTuple(h :: acc))
    }

  implicit def notSingletonCase[H, T <: HList, Acc <: HList](implicit
    reduce: Reduce[T, H :: Acc]): Reduce[H :: T, Acc] =
    (l, acc) => l match {
      case h :: t => reduce(t, h :: acc)
    }
}

def reduce[L <: HList, Acc <: HList](l: L, acc: Acc)(implicit 
  r: Reduce[L, Acc]): Nothing  = r(l, acc)

Now reduce((Option(R(1), 2), Option(R("S"), "s")).productElements, HNil) produces "could not find implicit value for parameter" but implicitly[Reduce[Option[(R[Int], Int)] :: Option[(R[String], String)] :: HNil, HNil]] compiles. If we substitute explicitly

reduce((Option(R(1), 2), Option(R("S"), "s")).productElements, HNil)(
  implicitly[Reduce[Option[(R[Int], Int)] :: Option[(R[String], String)] :: HNil, HNil]]
)

we'll have

Error:(52, 82) type mismatch;
 found   : Reduce[Option[(R[Int], Int)] :: Option[(R[String], String)] :: shapeless.HNil,shapeless.HNil]
 required: Reduce[Option[(R[Int], Int)] :: Option[(R[String], String)] :: shapeless.HNil,shapeless.HNil.type]
Note: shapeless.HNil >: shapeless.HNil.type, but trait Reduce is invariant in type Acc.
You may wish to define Acc as -Acc instead. (SLS 4.5)
  reduce((Option(R(1), 2), Option(R("S"), "s")).productElements, HNil)(implicitly[Reduce[Option[(R[Int], Int)] :: Option[(R[String], String)] :: HNil, HNil]])

So you should call it like

reduce((Option(R(1), 2), Option(R("S"), "s")).productElements, HNil : HNil)