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
– stefanobaghino, Commented May 18, 2018 at 13:58

Antot · Accepted Answer · 2018-05-18 13:50:53Z

5

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, 2018 at 13:50

Antot

3,9641 gold badge25 silver badges29 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

iTsaMe Over a year ago

This was just what i was looking for! Thank you! @Antot

PaulG Over a year ago

Just to point out: this solution is a recursive function, which is an ideal functional approach to iteration.

Levi Ramsey · Accepted Answer · 2018-05-18 13:53:37Z

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

answered May 18, 2018 at 13:53

Levi Ramsey

20.8k1 gold badge20 silver badges35 bronze badges

Comments

Hayk Hakobyan · Accepted Answer · 2018-05-18 13:57:51Z

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, 2018 at 13:57

Hayk Hakobyan

3092 silver badges8 bronze badges

1 Comment

Leo C Over a year ago

Nice solution but not really a railrec as there is a nested flatten call in the tail position.

stefanobaghino · Accepted Answer · 2018-05-18 18:06:28Z

2

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.

edited May 18, 2018 at 18:06

answered May 18, 2018 at 14:05

stefanobaghino

13.4k4 gold badges44 silver badges69 bronze badges

1 Comment

Antot Over a year ago

Well seen about complex +: vs Seq(complex) ++, List() vs Nil and .view. +1

Collectives™ on Stack Overflow

Flatten nested objects in Scala

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

Comments

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related