Уменьшить последовательность по частям

Question

У меня есть последовательность Seq[T], и я хочу сделать частичное сокращение. Например, для Seq[Int] я хочу получить Seq[Int], состоящий из самых длинных частичных сумм монотонных областей. Например:

val s = Seq(1, 2, 4, 3, 2, -1, 0, 6, 8)
groupMonotionic(s) = Seq(1 + 2 + 4, 3 + 2 + (-1), 0 + 6 + 8)

Я искал какой-то метод, например условное сгиб с сигнатурой fold(z: B)((B, T) => B, (T, T) => Boolean), где предикат указывает, где завершить агрегацию текущей суммы, но, похоже, в иерархии вычитаний Seq. 1009 нет ничего подобного. *

Каким было бы решение с использованием Scala Collection API и без использования изменяемых переменных?

Answer 1

Работает в Scala 2.13+ с cats

import scala.util.chaining._
import cats.data._
import cats.implicits._

val s = List(1, 2, 4, 3, 2, -1, 0, 6, 8)

def isLocalExtrema(a: List[Int]) =
    a.max == a(1) || a.min == a(1)

implicit class ListOps[T](ls: List[T]) {
  def multiSpanUntil(f: T => Boolean): List[List[T]] = ls.span(f) match {
    case (h, Nil) => List(h)
    case (h, t) => (h ::: t.take(1)) :: t.tail.multiSpanUntil(f)
  }
}

def groupMonotionic(groups: List[Int]) = groups match {
  case Nil => Nil
  case x  if x.length < 3 => List(groups.sum)      
  case _ =>

    groups
      .sliding(3).toList
      .map(isLocalExtrema)
      .pipe(false :: _ ::: List(false))
      .zip(groups)
      .multiSpanUntil(!_._1)
      .pipe(Nested.apply)
      .map(_._2)
      .value
      .map(_.sum)

}

println(groupMonotionic(s))
//List(7, 4, 14)

Answer 2

Вот один из многих способов сделать это (используя Scala 2.13 s List#unfold):

// val items = Seq(1, 2, 4, 3, 2, -1, 0, 6, 8)
items match {
  case first :: _ :: _ =>                // If there are more than 2 items
    List
      .unfold(items.sliding(2).toList) { // We slid items to work on pairs of consecutive items
        case Nil =>                      // No more items to unfold
          None                           // None signifies the end of the unfold
        case rest @ Seq(a, b) :: _ =>    // We span based on the sign of a-b
          Some(rest.span(x => (x.head - x.last).signum == (a-b).signum))
      }
      .map(_.map(_.last))                // back from slided pairs
      match { case head :: rest => (first :: head) :: rest }
  case _ =>                              // If there is 0 or 1 item
    items.map(List(_))
}
// List(List(1, 2, 4), List(3, 2, -1), List(0, 6, 8))

List.unfold повторяется до тех пор, пока функция развертывания обеспечивает Some. Он начинается с начального состояния, которое представляет собой список элементов, которые необходимо развернуть. На каждой итерации мы span определяем состояние (оставшиеся элементы развертываются) на основе знака разницы заголовка двух элементов. Развернутые элементы являются заголовочными элементами, имеющими одинаковую монотонность, а развернутое состояние становится остальными элементами.

List#span разбивает список на кортеж, первая часть которого содержит элементы, соответствующие примененному предикату, пока предикат не перестанет быть действительным. Вторая часть кортежа содержит остальные элементы. Который идеально соответствует ожидаемому типу возврата функции развертывания List.unfold, который равен Option[(A, S)] (в данном случае Option[(List[Int], List[Int])]).

Int.signum возвращает -1, 0 или 1 в зависимости от знака целого числа, к которому он применен.

Обратите внимание, что первый элемент должен быть возвращен в результате, так как у него нет предка, определяющего его знак (match { case head :: rest => (first :: head) :: rest }).

Чтобы применить сокращающую функцию (в данном случае сумму), мы можем отобразить конечный результат: .map(_.sum)

Answer 3

Вот один из способов использования foldLeft для обхода числового списка с помощью аккумулятора Tuple3 (listOfLists, prevElem, prevTrend), в котором хранятся previous element и previous trend для условной сборки list of lists в текущей итерации:

val list = List(1, 2, 4, 3, 2, -1, 0, 6, 8)

val isUpward = (a: Int, b: Int) => a < b

val initTrend = isUpward(list.head, list.tail.head)

val monotonicLists = list.foldLeft( (List[List[Int]](), list.head, initTrend) ){
  case ((lol, prev, prevTrend), curr) =>
    val currTrend = isUpward(curr, prev)
    if (currTrend == prevTrend)
      ((curr :: lol.head) :: lol.tail , curr, currTrend)
    else
      (List(curr) :: lol , curr, currTrend)
}._1.reverse.map(_.reverse)
// monotonicLists: List[List[Int]] = List(List(1, 2, 4), List(3, 2, -1), List(0, 6, 8))

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

monotonicLists.map(_.sum)
// res1: List[Int] = List(7, 4, 14)