12

有时我会花一些时间玩 Scala，尽管我无法在我自己的工作中使用它（到目前为止），但它的混合功能对我很有吸引力。对于踢球，我决定以最通用的方式尝试前几个99 Haskell 问题——对任何类型的适用集合进行操作并返回。前几个问题并不太难，但我发现自己完全被flatten. 我只是不知道如何输入这样的东西。

具体来说我的问题：是否可以编写一个类型安全的函数来展平任意嵌套SeqLike的 s？所以说，

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 问题集中的问题并不完全相同。我正在尝试编写一个函数，它不是扁平化异构列表，而是扁平化同质但嵌套的序列。

在网上搜索我找到了该问题的Scala 翻译，但它运行并返回 List[Any]。我是否正确，这需要某种类型的递归？还是我把它弄得比现在更难？

4

3 回答 3

13

The following works in Scala 2.10.0-M7. You will need to add extra cases for Array support, and perhaps refine it to have more specific output collection types, but I guess it can all be done starting from here:

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)
于 2012-08-29T00:07:54.970 回答
4

It seems like the right thing to do is just call .flatten the right number of times:

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)

Since Scala is typed, you always know ahead of time how deep the nesting goes for the specific variable. Since you know this ahead of time, there's not much value in handling arbitrary structure as if you were unsure of how many times .flatten needed to be called.

于 2012-08-28T14:49:26.433 回答
3

您面临着他们在 Haskell解决方案中描述的相同问题：Scala 中没有异构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]

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

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))

Of course, we could also have added this as a method directly to the NestedList trait.

于 2012-08-28T14:24:27.697 回答