Извлечение регионов из массива Scala

Question

Я действительно не знаю, как описать то, что я делаю, но этот пример должен помочь:

val vals = Array( (0, true), 
                  (1, true), 
                  (2,true), 
                  (3,true), 
                  (4,false), 
                  (5, true), 
                  (6, true), 
                  (7, false), 
                  (8, true), 
                  (9,true))

Я ищу, чтобы определить первый и последний элементы в каждом из 'истинных'регионов, хотя разделение массива при изменении значения может также работать.Я мог бы сделать это настоятельно, но как лучше всего это сделать в Scala?

Answer 1

Если вы не возражаете добавить какую-либо инфраструктуру для обработки функции groupedWhile, вы можете украсть ответ Рекса Керра о расширении коллекции scala . Используйте раздел, который обрабатывает массив, во второй части ответа.

Тогда это бриз:

scala> vals.groupedWhile(_._2 == _._2).filter(_.head._2 == true).map{g => 
  (g.head, g.last)}.foreach(println)

((0,true),(3,true))
((5,true),(6,true))
((8,true),(9,true))

Edit:

Я придумал решение, которое не требует groupedWhile. Он основан на использовании Iterator.iterate, который начинается с начального числа и неоднократно применяет функцию span для извлечения следующей группы элементов, имеющих то же логическое свойство. В этом случае семя является кортежем следующей группы и остатком для обработки:

type Arr = Array[(Int, Boolean)] // type alias for easier reading

val res = Iterator.iterate[(Arr, Arr)]((Array(), vals)){ case (same, rest) => 
  // repeatedly split in (same by boolean, rest of data)
  // by using span and comparing against head
  rest.span(elem => elem._2 == rest.head._2)
}.drop(1).takeWhile{ case (same, _) =>        // drop initial empty seed array
  same.nonEmpty                               // stop when same becomes empty
}.collect{ case (same, _) if same.head._2 == true =>
  // keep "true" groups and extract (first, last)
  (same.head, same.last)                     
}.foreach(println)                            // print result

Который печатает тот же результат, что и выше. Обратите внимание, что span для пустых массивов не вызывает предикат, поэтому мы не получим исключение для rest.head, если rest пусто.

Answer 2

@tailrec
def regions(l: Seq[(Int, Boolean)], nl : Seq[(Int, Int)]): Seq[(Int, Int)] = 
    if (l.isEmpty) nl
    else if (!l.head._2) regions(l dropWhile (!_._2), nl)
    else {
        val (first, rest) = l span (_._2)
        regions(rest, (first.head._1, first.last._1) +: nl)
    }

Взяв оригинальный ответ Даниэля и сделав хвост рекурсивным.

Answer 3

Для нерекурсивного решения вы можете сделать это:

val ss = (0, false) +: vals :+ (0, false) sliding 2 toList
val starts = ss filter (i => !i(0)._2 && i(1)._2) map (_(1))
val ends   = ss filter (i => !i(1)._2 && i(0)._2) map (_(0))

, который дает вам списки начальных и конечных элементов.

Для регионов вы можете просто сжать списки вместе:

scala> starts zip ends foreach println
((0,true),(3,true))
((5,true),(6,true))
((8,true),(9,true))

Answer 4

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

В данном конкретном случае, поскольку вы отбрасываете все подсписки false, вы можете специализироваться. Например:

def regions(l: Seq[(Int, Boolean)]): Seq[(Int, Int)] = 
  if (l.isEmpty) Seq.empty
  else if (!l.head._2) regions(l dropWhile (!_._2))
  else {
    val (first, rest) = l span (_._2)
    (first.head._1, first.last._1) +: regions(rest)
  }

Итеративно, я бы, вероятно, использовал unfold от Scalaz. Код выглядит примерно так же:

def regions(l: Seq[(Int, Boolean)]): Seq[(Int, Int)] = {
  l.unfold[Seq, (Int, Int)] { ll =>
    val tl = ll dropWhile (!_._2)
    if (tl.isEmpty) None
    else {
      val (first, rest) = tl span (_._2)
      Some(((first.head._1, first.last._1), rest))
    }
  }
}

Answer 5

Раствор со складкой:

val result = vals.foldLeft(List(List.empty[Int])) {
  case (head::tail, (x, true)) => (x::head)::tail
  case (xs, (_, false)) => Nil::xs
}.map { xs => xs.head::xs.last::Nil }
result: List[List[Int]] = List(List(9, 8), List(6, 5), List(3, 0))

каждый раз, когда мы сталкиваемся с ложью, мы добавляем новый список в аккумулятор.

Следующая версия еще более эффективна (но, возможно, не так понятна):

val result = vals.foldLeft(List(List.empty[Int])) {
  case (head::tail, (x, true)) => head match {
    case Nil => (x::Nil)::tail
    case last::Nil => (x::last::Nil)::tail
    case first::last => (x::last)::tail
  }
  case (xs, (_, false)) => Nil::xs
}
result: List[List[Int]] = List(List(9, 8), List(6, 5), List(3, 0))

Answer 6

Использование foldLeft:

type Region = (Int, Boolean)
type RegionPair = (Region, Region)
type Acc = (Option[Region], Region, List[RegionPair])
val initAcc: Acc = (None, (0, false), Nil) //optional first, dummy last, empty regions

def groupRegions(s: Acc, region: Region): Acc = {
  val (first, last, regions) = s
  first match {
    case Some(f) => 
      if (!region._2) (None, last, (f, last) :: regions)
      else (first, region, regions)
    case _ => (Some(region), region, regions)
  } 
}

val (remFirst, remLast, regions) = (initAcc /: vals)(groupRegions)

val solution = remFirst map ((_, remLast) :: regions) getOrElse regions //reverse if you want