Higher order operations with flattened tuples in scala

Question

I've recently come across a problem. I'm trying to flatten "tail-nested" tuples in a compiler-friendly way, and I've come up with the code below:

implicit def FS[T](x: T): List[T] = List(x)
implicit def flatten[T,V](x: (T,V))(implicit ft: T=>List[T], fv: V=>List[T]) = 
  ft(x._1) ++ fv(x._2)

This above code works well for flattening tuples I am calling "tail-nested" like the ones below.

flatten((1,2)) -> List(1,2)
flatten((1,(2,3))) -> List(1,2,3)
flatten((1,(2,(3,4)))) -> List(1,2,3,4)

However, I seek to make my solution more robust. Consider a case where I have a list of these higher-kinded "tail-nested" tuples.

val l = List( (1,2), (1,(2,3)), (1,(2,(3,4))) )

The inferred type signature of this would be List[(Int, Any)] and this poses a problem for an operation such as map, which would fail with:

error: No implicit view available from Any => List[Int]

This error makes sense to me because of the nature of my recursive implicit chain in the flatten function. However, I was wondering: is there any way I can make my method of flattening the tuples more robust so that higher order functions such as map mesh well with it?

EDIT:

As Bask.ws pointed out, the Product trait offers potential for a nice solution. The below code illustrates this:

def flatten(p: Product): List[_] = p.productIterator.toList.flatMap {x => x match {
  case pr: Product => flatten(pr)
  case _ => List(x)
}}

The result type of this new flatten call is always List[Any]. My problem would be solved if there was a way to have the compiler tighten this bound a bit. In parallel to my original question, does anyone know if it is possible to accomplish this?

Answer 1

UPD Compile-time fail solution added

I have one solution that may suit you. Types of your first 3 examples are resolved in compile time: Int, Tuple2[Int, Int], Tuple2[Int, Tuple2[Int, Int]]. For you example with the list you have heterogeneous list with actual type List[(Int, Any)] and you have to resolve the second type in runtime or it maybe can be done by macro. So you may want to actually write implicit def flatten[T](x: (T,Any)) as your error advises you

Here is the fast solution. It gives a couple of warnings, but it works nicely:

  implicit def FS[T](x: T): List[T] = List(x)

  implicit def FP[T](x: Product): List[T] = {
    val res = (0 until x.productArity).map(i => x.productElement(i) match {
      case p: Product => FP[T](p)
      case e: T => FS(e)
      case _ => sys.error("incorrect element")
    })
    res.toList.flatten
  }

  implicit def flatten[T](x: (T,Any))(implicit ft: T=>List[T], fp: Product =>List[T]) =
    ft(x._1) ++ (x._2 match {
      case p: Product => fp(p)
      case t: T => ft(t)
    })


  val l = List( (1,2), (1,(2,3)), (1,(2,(3,4))) )

  scala> l.map(_.flatten)
  res0: List[List[Int]] = List(List(1, 2), List(1, 2, 3), List(1, 2, 3, 4))

UPD I have researched problem a little bit more, and I have found simple solution to make homogeneus list, which can fail at compile time. It is fully typed without Any and match and looks like compiler now correctly resolves nested implicits

  case class InfiniteTuple[T](head: T, tail: Option[InfiniteTuple[T]] = None) {
    def flatten: List[T] = head +: tail.map(_.flatten).getOrElse(Nil)
  }

  implicit def toInfiniteTuple[T](x: T): InfiniteTuple[T] = InfiniteTuple(x)

  implicit def toInfiniteTuple2[T, V](x: (T, V))(implicit ft: V => InfiniteTuple[T]): InfiniteTuple[T] =
    InfiniteTuple(x._1, Some(ft(x._2)))

  def l: List[InfiniteTuple[Int]] = List( (1,2), (1,(2,3)), (1,(2,(3,4)))) //OK

  def c: List[InfiniteTuple[Int]] = List( (1,2), (1,(2,3)), (1,(2,(3,"44"))))

  //Compile-time error
  //<console>:11: error: No implicit view available from (Int, (Int, java.lang.String)) => InfiniteTuple[Int]

Then you can implement any flatten you want. For example, one above:

scala> l.map(_.flatten)
res0: List[List[Int]] = List(List(1, 2), List(1, 2, 3), List(1, 2, 3, 4))