Scala group consecutive elements in list where function is true

Question

Consider the following list (0,10,12,7,-10,7,2,3,-2,4)

I would like to have a function that groups the above list into sublists where the function (x:Int)=>x>0 is true to get the desired result

((0,10,12,7),(7,2,3),(4))

I have found the pack function which groups consecutive identical elements in a list.

  def pack[T](xs: List[T]): List[List[T]] = xs match {
    case Nil      => Nil
    case x :: xs1 =>
      val (first, rest) = xs span (y => x == y)
      first :: pack(rest)
  }

This is almost what I need but I was not able to extend it to my current problem.

Answer 1

First naive version that comes to my mind (there's definitely room for improvement)

def pack(xs: List[Int]): List[List[Int]] = xs match {
  case Nil => Nil
  case _ =>
    val (first, rest) = xs.span(_ >= 0)
    first :: pack(rest.dropWhile(_ < 0))
}

Example:

scala> pack(List(0, 10, 12, 7, -10, 7, 2, 3, -2, 4))
res0: List[List[Int]] = List(List(0, 10, 12, 7), List(7, 2, 3), List(4))

Answer 2

A similar approach based in span, in this case called multiSpan for multiple partitions following a predicate; hence for

val a = List(0,10,12,7,-10,7,2,3,-2,4)

by negating the predicate

a.multiSpan( _ < 0)
List(List(0, 10, 12, 7), List(-10, 7, 2, 3), List(-2, 4))

and so the desired output may be achieved with

a.multiSpan( _ < 0).map( _.dropWhile(_ < 0))
List(List(0, 10, 12, 7), List(7, 2, 3), List(4))

To convey with the statement consider thus

def pack[T](xs: List[T]): List[List[T]] = 
  xs.multiSpan( _ < 0).map( _.dropWhile(_ < 0))

Answer 3

You can also use foldLeft with additional binary variable that is true when the next positive element should be appended to the last list:

def pack(xs: List[Int], f: (Int => Boolean)): List[List[Int]] = {
  xs.foldLeft((List[List[Int]](), false)) {
    case ((acc, false), el) if f(el) => (acc :+ List(el), true)
    case ((acc, true), el) if f(el) => (acc.init :+ (acc.last :+ el) , true)
    case ((acc, _) , el) => (acc, false)
  }._1
}

Answer 4

If everyone is posting their version, I'll add my own, too.

Uses foldLeft to traverse the list just once and Vector for efficient functional append. The final result is a List[List[A]], though:

/**
 * scala> val l = List(0, 10, 12, 7, -10, 7, 2, 3, -2, 4)
 * scala> groupFilter(l)(_ >= 0)
 * res0: List[List[Int]] = List(List(0, 10, 12, 7), List(7, 2, 3), List(4))
 */
def groupFilter[A](list: List[A])(predicate: A => Boolean): List[List[A]] = {
  // The accumulator is a tuple containing the already grouped
  // previous values and the the current group being built.
  val seed = Vector.empty[List[A]] -> Vector.empty[A]

  val (prevGroups, lastGroup) = list.foldLeft(seed) {
    case (groups @ (prevGroups, lastGroup), a) =>
      if (predicate(a))
        prevGroups -> (lastGroup :+ a)
      else if (lastGroup.nonEmpty)
        (prevGroups :+ lastGroup.toList) -> Vector.empty
      else
        groups
  }

  (prevGroups :+ lastGroup.toList).toList
}

And a version that uses foldRight and List's :: to keep time complexity low:

def groupFilter[A](list: List[A])(predicate: A => Boolean): List[List[A]] = {
  val seed = List.empty[List[A]] -> List.empty[A]

  val (prevGroups, lastGroup) = list.foldRight(seed) {
    case (a, groups @ (prevGroups, lastGroup)) =>
      if (predicate(a))
        prevGroups -> (a :: lastGroup)
      else if (lastGroup.nonEmpty)
        (lastGroup :: prevGroups) -> List.empty
      else
        groups
  }

  lastGroup :: prevGroups
}

One last version using explicit tail-recursion:

def groupFilter[A](list: List[A])(predicate: A => Boolean): List[List[A]] = {
  @annotation.tailrec
  def loop(list: List[A], prevGroups: Vector[List[A]], lastGroup: Vector[A]): List[List[A]] = {
    list match {
      case Nil =>
        (prevGroups :+ lastGroup.toList).toList
      case head :: tail if predicate(head) =>
        loop(tail, prevGroups, lastGroup :+ head)
      case _ :: tail if lastGroup.nonEmpty =>
        loop(tail, prevGroups :+ lastGroup.toList, Vector.empty)
      case _ :: tail =>
        loop(tail, prevGroups, lastGroup)
    }
  }

  loop(list, Vector.empty, Vector.empty)
}