通用的，类型安全的方式来扁平化Scala中任意嵌套的集合？

Question

有时，我会花一些时间使用Scala，尽管(到目前为止)我无法在自己的工作中使用它，但Scala的混合特性对我很有吸引力。首先，我决定以最通用的方式尝试前几个99 Haskell Problems -操作并返回任何类型的适用集合。前几个问题并不是很难，但我发现自己完全被flatten阻碍了。我就是想不出怎么打字。

具体来说，我的问题是:有没有可能编写一个类型安全的函数来扁平化任意嵌套的SeqLike？所以，比如说，

flatten(List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12))))

将会返回

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12): List[Int]

？请注意，这与Haskell和Scala问题集中的问题不完全相同；我正在尝试编写一个函数，该函数不会展平异构列表，而是展平同构但嵌套的序列。

在网上搜索，我找到了这个问题的translation into Scala，但它操作并返回一个ListAny。这需要某种类型的递归，我说的对吗？还是说我让这件事变得比实际更难？

Answer 1

下面的代码适用于Scala 2.10.0-M7。您将需要为Array支持添加额外的案例，也许还需要对其进行改进，使其具有更具体的输出集合类型，但我猜从这里开始可以完成所有工作：

sealed trait InnerMost {
  implicit def innerSeq[A]: CanFlatten[Seq[A]] { type Elem = A } =
    new CanFlatten[Seq[A]] {
      type Elem = A
      def flatten(seq: Seq[A]): Seq[A] = seq
    }
}
object CanFlatten extends InnerMost {
  implicit def nestedSeq[A](implicit inner: CanFlatten[A]) 
  : CanFlatten[Seq[A]] { type Elem = inner.Elem } =
    new CanFlatten[Seq[A]] {
      type Elem = inner.Elem
      def flatten(seq: Seq[A]): Seq[inner.Elem] =
        seq.flatMap(a => inner.flatten(a))
    }
}
sealed trait CanFlatten[-A] {
  type Elem
  def flatten(seq: A): Seq[Elem]
}

implicit final class FlattenOp[A](val seq: A)(implicit val can: CanFlatten[A]) {
  def flattenAll: Seq[can.Elem] = can.flatten(seq)
}

// test        
assert(List(1, 2, 3).flattenAll == Seq(1, 2, 3))
assert(List(Seq(List(1, 2, 3), List(4, 5, 6)), Seq(List(7, 8, 9),
                List(10, 11, 12))).flattenAll == (1 to 12).toSeq)

Answer 2

看起来正确的做法是调用.flatten正确的次数：

scala> val x = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))
x: List[Array[List[Int]]] = List(Array(List(1, 2, 3), List(4, 5, 6)), Array(List(7, 8, 9), List(10, 11, 12)))

scala> x.flatten.flatten
res0: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

因为Scala是类型化的，所以您总是提前知道特定变量的嵌套深度。由于您事先就知道这一点，所以处理任意结构并没有多大价值，就好像您不确定需要调用多少次.flatten一样。

Answer 3

你正面临着他们在Haskell中描述的同样的问题：solution中没有异构的List。幸运的是，您可以遵循他们在Haskell解决方案中所走的完全相同的路径。

定义一些可以嵌套的数据类型：

sealed trait NestedList[A]
case class Elem[A](a: A) extends NestedList[A]
case class AList[A](a: List[NestedList[A]]) extends NestedList[A]

然后为该类型编写一个通用的扁平函数：

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x :: xs) => flatten(x) ::: flatten(AList(xs))
  case AList(Nil) => Nil
}

甚至是

def flatten[A](l: NestedList[A]): List[A] = l match {
  case Elem(x) => List(x)
  case AList(x) => x.flatMap(flatten)
}

用法：

flatten(AList(Elem(1) :: Elem(2) :: AList(Elem(3) :: Nil) :: Nil))

当然，我们也可以将其作为方法直接添加到NestedList特征中。