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:

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

In the time it took me to test my solution the count of occurrences of the word `flat` in this page has grown to 32. :-) — stefanobaghino, May 18 '18 at 13:58

score 4 · Accepted Answer · answered May 18 '18 at 13:50

4

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

answered May 18 '18 at 13:50

Antot

3,904
1
21
27

This was just what i was looking for! Thank you! @Antot – iTsaMe May 18 '18 at 14:33
Just to point out: this solution is a recursive function, which is an ideal functional approach to iteration. – PaulG Jul 22 '19 at 21:54

score 2 · Answer 2 · answered May 18 '18 at 13:53

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

score 2 · Answer 3 · answered May 18 '18 at 13:57

2

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

answered May 18 '18 at 13:57

Hayk Hakobyan

309
2
8

2

Nice solution but not really a `railrec` as there is a nested `flatten` call in the tail position. – Leo C May 18 '18 at 17:09

stefanobaghino · Answer 4 · 2018-05-18T18:06:28.330

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.

Well seen about `complex +:` vs `Seq(complex) ++`, `List()` vs `Nil` and `.view`. +1 — Antot, May 18 '18 at 16:07

Flatten nested objects in Scala

4 Answers4