Сведение вложенных объектов в Scala

Учитывая сложный объект, подобный следующему:

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 объектов, подтянув вверх всех детей/внуков.

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

Есть ли у вас какие-либо выводы / идеи о том, как я могу это сделать?

Другие решения, которые я пробовал, похоже, делают только простое вложение списков. Что я пробовал:

Кажется, все они приводят к тому же списку, с которого я начал.


flatmap scala flatten
person iTsaMe    schedule 18.05.2018    source источник
comment
За то время, которое мне понадобилось, чтобы проверить свое решение, количество вхождений слова flat на этой странице выросло до 32. :-)   -  person stefanobaghino    schedule 18.05.2018

Ответы (4)


arrow_upward
3
arrow_downward

Сложность выравнивания входного 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())
  )
person Antot    schedule 18.05.2018
comment
Это было именно то, что я искал! Спасибо! @Антот - person iTsaMe; 18.05.2018
comment
Просто отметим: это решение представляет собой рекурсивную функцию, которая является идеальным функциональным подходом к итерации. - person PaulG; 23.07.2019

arrow_upward
2
arrow_downward 

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()))
person Levi Ramsey    schedule 18.05.2018

arrow_upward
2
arrow_downward

Использование хвостовой рекурсии.

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())
person Hayk Hakobyan    schedule 18.05.2018
comment
Хорошее решение, но на самом деле это не railrec, так как в хвостовой позиции есть вложенный вызов flatten. - person Leo C; 18.05.2018

arrow_upward
2
arrow_downward

Мое решение в основном похоже на уже опубликованные, но позволяет избежать (не столь существенной) неэффективности помещения элемента 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))

Обратите внимание, что я также отложил замену элементов nested пустым списком (Nil), разделив их по отношению к фактическому выравниванию, но при этом избегая ненужных двойных проходов с использованием view (подробнее об этом здесь).

Вы можете поиграть с этим решением на Scastie.

person stefanobaghino    schedule 18.05.2018
comment
Хорошо видно о complex +: против Seq(complex) ++, List() против Nil и .view. +1 - person Antot; 18.05.2018