Flatten nested objects in Scala

Question

Given a complex object like the following:

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

In action this can turn into something like this:

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

I need to turn it into a flat list of Complex objects, pulling all the children/grandchildren up.

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

Do you have any leads/ideas on how I can accomplish this?

The other solutions I have tried seem to only do simple nesting of lists. Things I've tried:

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

These all seem to yield the same list I started with.

Answer 1

The difficulty in flattening of the input Seq here is that it is necessary to remove the nested references in the resulting list. This can be done by copying the original object with nested = empty list and flattening all the sequences:

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

which gives:

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

Using Tail Recursion.

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

My solution is mostly like those already posted, but avoids the (not so significant) inefficiency of putting the head element in a singleton collection when flattening a single element:

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

as opposed to

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

to then be used as follows:

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

Notice that I also deferred substituting the nested elements with an empty list (Nil), decoupling with respect to the actual flattening, while still avoiding unneeded double passes leveraging view (more on that here).

You can play around with this solution on Scastie.