Какой самый чистый способ собирать дочерние элементы вложенных списков в Scala?

#scala

Вопрос:

Представьте, что у меня есть вложенный список списков 3 или более уровней (или любая другая коллекция), например

 val items: Seq[Seq[Seq[Int]]] = Seq(Seq(Seq(1,2,3), Seq(4,5,6), Seq(4,5,6)), Seq(Seq(1,2,3), Seq(4,5,6), Seq(4,5,6)))

Каков самый чистый способ обхода этой коллекции и сбора дочерних элементов на основе логического правила.

Например, учитывая следующее правило

 (item) => item % 2 == 0

Он возвращает

  Seq(2,4,6,4,6,2,4,6,4,6)

без плоского отображения / выравнивания списка или использования изменяемых коллекций!

1. items имеет тип Seq[Any] . Вопрос, который вы должны задать себе: «Могу ли я использовать / получить что-то более типобезопасное?»

2. @Jubobs, извините — я написал это без запуска в консоли. Но я уверен, что вы достаточно умны, чтобы понять, что я имею в виду.

3. Является ли уровень вложенности «3 или более» согласованным для любого данного экземпляра? Если нет, то @Jubobs прав, вы имеете дело с типом Seq[Any] .

4. Почему вы хотите избежать flatMap ? Переход от вложенного списка к плоскому списку будет (почти?) неизменно предполагает какое-то сглаживание

5. Рассмотрено использование scalaz.Tree или любая другая древовидная структура вместо этого?

Ответ №1:

Некоторое время назад кто-то задавал аналогичный вопрос о вложенных Option s. Я предоставил общий шаблон решения, который должен работать для любой монадической структуры.

Просто убедитесь, что у вас есть вложенный монадический тип… это не будет работать с Seq[Any]

Я просто расширю это, чтобы разобраться с Seq

 import scala.language.higherKinds

case class Flattener[W[_], WW, T](fn : WW => W[T])

implicit def seqRecFlattenFn[WW, T](
  implicit f: Flattener[Seq, WW, T] = Flattener((ww: WW) => Seq(ww))
) = Flattener((ww: Seq[WW]) => ww.flatMap(f.fn))

def seqRecursiveFlatten[WW, T](www: Seq[WW])(
  implicit f : Flattener[Seq, Seq[WW], T]
) = f.fn(www)

val nestedSeq1 = Seq(Seq(Seq(Seq(5, 10), Seq(20, 30))))
// nestedSeq1: Seq[Seq[Seq[Seq[Int]]]] = List(List(List(List(5, 10), List(20, 30))))

val flatSeq1 = seqRecursiveFlatten(nestedSeq1)
// flatSeq1: Seq[Int] = List(5, 10, 20, 30)

val nestedSeq2 = Seq(Seq(Seq(Seq(Seq(Seq(Seq(5, 10), Seq(20, 30)))))))
// nestedSeq2: Seq[Seq[Seq[Seq[Seq[Seq[Seq[Int]]]]]]] = List(List(List(List(List(List(List(5, 10), List(20, 30)))))))

val flatSeq2 = seqRecursiveFlatten(nestedSeq)
// flatSeq2: Seq[Int] = List(5, 10, 20, 30)

Теперь у вас есть плоский Seq, поэтому применяйте любую фильтрацию или что угодно, что вы хотите.

Ответ №2:

Если вам нужно иметь дело с произвольно вложенными списками, то вам придется иметь дело с Seq[Any]:

 def flatFilter(src: Seq[Any], pred: (Int => Boolean)): Seq[Int] = {
  if (src.isEmpty) 
    Seq.empty
  else src.head match {
    case car: Seq[Any] =>
      flatFilter(car, pred)    flatFilter(src.tail, pred)
    case car: Int =>
      if (pred(car)) 
        car  : flatFilter(src.tail, pred)
      else 
        flatFilter(src.tail, pred)
    case _ => flatFilter(src.tail, pred)
  }
}

1. Нет… вы можете сохранить его типобезопасным. Нет необходимости привлекать Any s. Посмотрите на мой ответ.

2. Если существует определенный уровень вложенности, то да, вы можете сохранить его в безопасности. Однако нет, если это связано с произвольной вложенностью. Отредактировано, чтобы отразить это.