Reduce sequence by parts

user_2786156 0
Viewed 782

I have a sequence Seq[T] and I want to do partial reduce. For example for a Seq[Int] I want to get Seq[Int] consisting of the longest partial sums of monotonic regions. For example:

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

I was looking for some method like conditional fold with the signature fold(z: B)((B, T) => B, (T, T) => Boolean) where the predicate states for where to terminate current sum aggregation, but it seems there is no something like that in the subtrait hierarchy of Seq.

What would be a solution using Scala Collection API and without using mutable variables?

scala collections
3 Answers

Here is one way amongst many to do this (using 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 iterates as long as the unfolding function provides Some. It starts with an initial state which is the list of items to unfold. At each iteration, we span the state (remaining elements to unfold) based on the sign of the heading two elements difference. The unfolded elements are heading items sharing the same monotony and the unfolding state becomes the other remaining elements.

List#span splits a list into a tuple whose first part contains elements matching the predicate applied until the predicate stops being valid. The second part of the tuple contains the rest of the elements. Which fits perfectly the expected return type of List.unfold's unfolding function, which is Option[(A, S)] (In this case Option[(List[Int], List[Int])]).

Int.signum returns -1, 0 or 1 depending on the sign of the integer it's applied on.

Note that the first item has to be put back in the result as it hasn't an ancestor determining its signum (match { case head :: rest => (first :: head) :: rest }).

To apply the reducing function (in this case a sum), we can map the final result: .map(_.sum)

user_92971440

Works in Scala 2.13+ with 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)
user_83627650

Here's one way using foldLeft to traverse the numeric list with a Tuple3 accumulator (listOfLists, prevElem, prevTrend) that stores the previous element and previous trend to conditionally assemble a list of lists in the current iteration:

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

To sum the individual nested lists:

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