在 Scala 中展平嵌套对象

Question

给定一个如下所示的复杂对象：

case class Complex
(
  id: Long,
  name: String,
  nested: Seq[Complex]
)

在实际操作中，这可以变成这样：

val stuff =
  List(
    Complex(1, "name1",
      List(
        Complex(2, "name2", List()),
        Complex(3, "name3",
          List(
            Complex(4, "name4", List())
          )
        )
      )
    )
  )

我需要将其变成 Complex 对象的平面列表，将所有 children/grandchildren 拉起来。

val flattened =
  List(
    Complex(1, "name1", List()),
    Complex(2, "name2", List()),
    Complex(3, "name3", List()),
    Complex(4, "name4", List()),
  )

你有什么 leads/ideas 我可以如何做到这一点吗？

我尝试过的其他解决方案似乎只能进行简单的列表嵌套。我尝试过的事情：

How does this recursive List flattening work?
Generic, type-safe way to flatten arbitrarily nested collections in Scala?

这些似乎都产生了我开始时使用的相同列表。

Answer 1

这里对输入Seq进行扁平化的难点在于需要移除结果列表中的嵌套引用。这可以通过使用 nested = 空列表复制原始对象并展平所有序列来完成：

def flatten(obj: Complex): Seq[Complex] = {
  val unnested = obj.copy(nested = List())
  Seq(unnested) ++ obj.nested.flatMap(flatten)
}

println(stuff.flatMap(flatten))

List(
  Complex(1,name1,List()),
  Complex(2,name2,List()),
  Complex(3,name3,List()),
  Complex(4,name4,List())
  )

Answer 2

def flattenComplex(c: Complex): Seq[Complex] = {
  if (c.nested.isEmpty) Seq(c)
  else Seq(c.copy(nested = Nil)) ++ c.nested.flatMap(flattenComplex _)
}

给出：

scala> stuff.flatMap(flattenComplex _)
res0: List[Complex] = List(Complex(1,name1,List()), Complex(2,name2,List()), Complex(3,name3,List()), Complex(4,name4,List()))

Answer 3

使用尾递归。

def flatten(source: Seq[Complex], dest: List[Complex]): List[Complex] = source match {
  case Nil => dest
  case x :: xs => flatten(xs, flatten(x.nested, dest :+ x.copy(nested = Nil)))
}
flatten(stuff, List())

Answer 4

我的解决方案与那些已经发布的解决方案大体相同，但避免了在展平单个元素时将 head 元素放入单例集合中的（不是很重要的）低效率：

def flatten(complex: Complex): Seq[Complex] =
  complex +: complex.nested.flatMap(flatten)

相对于

def flatten(complex: Complex): Seq[Complex] =
  Seq(complex) ++ complex.nested.flatMap(flatten)

然后按如下方式使用：

stuff.view.flatMap(flatten).map(_.copy(nested = Nil))

请注意，我还推迟了用空列表 (Nil) 替换 nested 元素，与实际展平相关的解耦，同时仍然避免利用 view 进行不必要的双重传递（更多关于 here）。

您可以试用此解决方案 on Scastie。

在 Scala 中展平嵌套对象

Flatten nested objects in Scala

scala

flatten

flatmap