how to create list consecutive values of positive or negative in scala

Question

list consecutive values of positive or negative in scala

val a = List(1,1,2,3,-1,2,3,4,-1,-2,-3)  //input
val z = List(List(1,2,3),List(-1),List(2,3,4),List(-1,-2,-3))  //expected

I tried splinting list with following code.

val sd = a.span(_>=0) match {
  case (left, Nil)   => left
  case (left, right) => left ++ ( right.filter(_>=0)) 
}

Answer 1

Here is a solution with foldLeft

def consecutiveLists(as : List[Int]) : List[List[Int]] =
  as.foldLeft(List[List[Int]](List[Int]())) ((a,b) => {
    val index = a.size - 1
    val currentList = a.last

    if(b >= 0 && (currentList.isEmpty || currentList.last < 0)) {
      a :+ List(b)
    } else if(b >=0 && (currentList.isEmpty || currentList.last >= 0)) {
      a.updated(index, currentList :+ b)
    } else if(b < 0 && (currentList.isEmpty || currentList.last >=0)) {
      a :+ List(b)
    } else {
      a.updated(index, currentList :+ b)
    }
  })

Testing:

consecutiveLists(List(1,1,2,3,-1,2,3,4,-1,-2,-3))
consecutiveLists(List(-1,-2,1,1,2,3,-1,2,3,4,-1,-2,-3))
consecutiveLists(List(-1))
consecutiveLists(List(-1,1,-1,1,2,-1,-1))

res0: List[List[Int]] = List(List(), List(1, 1, 2, 3), List(-1), List(2, 3, 4), List(-1, -2, -3))
res1: List[List[Int]] = List(List(), List(-1, -2), List(1, 1, 2, 3), List(-1), List(2, 3, 4), List(-1, -2, -3))
res2: List[List[Int]] = List(List(), List(-1))
res3: List[List[Int]] = List(List(), List(-1), List(1), List(-1), List(1, 2), List(-1, -1))

Notes:

• The result will always have an empty list as guard value. a drop(1) can get rid of this

• The four conditions can be simplified to two. I have not simplified it more to show the underlying logic:

Look at the last list, if the current value has opposite sign than the last list, create new list, otherwise just append the current value to the last list. There are possibly other ways to simplify it even more.

• It could be the case that List[List[Int]] is not the best data structure for this fold. Array[List[Int]] or Vector[List[Int]] could be better options.

EDIT: Here is the simplified version:

as.foldLeft(List[List[Int]](List[Int]())) ((a,b) => {
    val index = a.size - 1
    val currentList = a.last

    if((b >= 0 && (currentList.isEmpty || currentList.last < 0)) ||
      (b < 0 && (currentList.isEmpty || currentList.last >=0))) {
      a :+ List(b)
    } else {
      a.updated(index, currentList :+ b)
    }
  })

EDIT 2: Here is another try at simplification. I am using queues which guarantee O(1) addition of items. For the holding list, I am using vector, since this list can be both updated and inserted into. Also, the check for empty list has been removed by making sure the fold entry argument is never empty.

import scala.collection.immutable.Queue
type QI = Queue[Int]

def consecutiveLists(as : List[Int]) : Vector[QI] =
  if(as.isEmpty) 
    Vector.empty[QI]
  else
    as.drop(1).foldLeft(Vector[QI](Queue[Int](as.head))) ((a,b) => {
      val currentList = a.last

      if((b >= 0 && currentList.last < 0) ||
        (b < 0 && currentList.last >=0)) {
        a :+ Queue(b)
      } else {
        a.updated(a.size - 1, currentList :+ b)
      }
    })

Answer 2

IMHO, always the best way to manipulate a List is using tail-recursive algorithms.

sealed trait Sign

object Sign {
  final case object Positive extends Sign
  final case object Negative extends Sign
  final case object Neutral extends Sign

  def of(i: Int): Sign =
    if (i > 0) Positive
    else if (i < 0) Negative
    else Neutral
}

def extractBySign(sign: Sign)(list: List[Int]): (List[Int], List[Int]) = {
  @annotation.tailrec
  def loop(remaining: List[Int], acc: List[Int]): (List[Int], List[Int]) =
    remaining match {
      case Nil =>
        acc.reverse -> Nil

      case x :: xs if (Sign.of(x) == sign) =>
        loop(remaining = xs, x :: acc)

      case list =>
        acc.reverse -> list
    }

  loop(remaining = list, acc = List.empty)
}

def splitBySign(list: List[Int]): List[List[Int]] = {
  @annotation.tailrec
  def loop(remaining: List[Int], acc: List[List[Int]]): List[List[Int]] =
    remaining match {
      case x :: xs =>
        val sign = Sign.of(x)  
        val (list, newRemaining) = extractBySign(sign)(x :: xs)
        loop(newRemaining, list :: acc)   

      case Nil =>
        acc.reverse
    }

  loop(remaining = list, acc = List.empty)
}