scala - Scala 中扁平元组的高阶操作

Question

我最近遇到了一个问题。我试图以一种对编译器友好的方式扁平化“尾嵌套”元组，我想出了下面的代码:

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)

上面的代码适用于扁平化元组，我称之为“尾嵌套”，如下面的。

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

但是，我试图使我的解决方案更加健壮。考虑一个案例，我有一个这些高级“尾嵌套”元组的列表。

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

推断的类型签名将是 List[(Int, Any)]这对诸如 map 的操作造成了问题。 ，这将失败:
error: No implicit view available from Any => List[Int]
由于我在 flatten 函数中递归隐式链的性质，这个错误对我来说很有意义。但是，我想知道:有什么方法可以使我的扁平元组方法更健壮，以便更高阶的函数，例如 map配合得好吗？

编辑:

正如 Bask.ws 所指出的，产品特性提供了一个很好的解决方案的潜力。下面的代码说明了这一点:

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

这个新的 flatten 调用的结果类型总是 List[Any]。如果有办法让编译器稍微收紧这个界限，我的问题就会得到解决。与我原来的问题并行，有谁知道是否有可能做到这一点？

Answer 1

UPD 添加了编译时失败解决方案

我有一种可能适合您的解决方案。前 3 个示例的类型在编译时解析:Int, Tuple2[Int, Int], Tuple2[Int, Tuple2[Int, Int]]。对于您的列表示例，您有实际类型为 List[(Int, Any)] 的异构列表，您必须在运行时解析第二种类型，或者可以通过宏来完成。所以你可能真的想写 implicit def flatten[T](x: (T,Any))正如您的错误所提示的那样

这是快速解决方案。它给出了几个警告，但效果很好:

  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
我对问题进行了更多研究，并且找到了制作同构列表的简单解决方案，该解决方案可能会在编译时失败。它是完全类型化的，没有 Any 和 match，看起来编译器现在可以正确解析嵌套的隐式

  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]

然后你可以实现你想要的任何扁平化。例如上面的一个:

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