Scala Split Seq or List by Delimiter

Question

Let's say I have a sequence of ints like this:

val mySeq = Seq(0, 1, 2, 1, 0, -1, 0, 1, 2, 3, 2)

I want to split this by let's say 0 as a delimiter to look like this:

val mySplitSeq = Seq(Seq(0, 1, 2, 1), Seq(0, -1), Seq(0, 1, 2, 3, 2))

What is the most elegant way to do this in Scala?

Answer 1

This works alright

mySeq.foldLeft(Vector.empty[Vector[Int]]) {
  case (acc, i) if acc.isEmpty => Vector(Vector(i))
  case (acc, 0) => acc :+ Vector(0)
  case (acc, i) => acc.init :+ (acc.last :+ i)
}

where 0 (or whatever) is your delimiter.

Answer 2

Efficient O(n) solution

Tail-recursive solution that never appends anything to lists:

def splitBy[A](sep: A, seq: List[A]): List[List[A]] = {
  @annotation.tailrec
  def rec(xs: List[A], revAcc: List[List[A]]): List[List[A]] = xs match {
    case Nil => revAcc.reverse
    case h :: t => 
      if (h == sep) {
        val (pref, suff) = xs.tail.span(_ != sep)
        rec(suff, (h :: pref) :: revAcc)
      } else {
        val (pref, suff) = xs.span(_ != sep)
        rec(suff, pref :: revAcc)
      }
  }
  rec(seq, Nil)
}

val mySeq = List(0, 1, 2, 1, 0, -1, 0, 1, 2, 3, 2)
println(splitBy(0, mySeq))

produces:

List(List(0, 1, 2, 1), List(0, -1), List(0, 1, 2, 3, 2))

It also handles the case where the input does not start with the separator.

---

For fun: Another O(n) solution that works for small integers

This is more of warning rather than a solution. Trying to reuse String's split does not result in anything sane:

val mySeq = Seq(0, 1, 2, 1, 0, -1, 0, 1, 2, 3, 2)
val z = mySeq.min
val res = (mySeq
  .map(x => (x - z).toChar)
  .mkString
  .split((-z).toChar)
  .map(s => 0 :: s.toList.map(_.toInt + z)
).toList.tail)

It will fail if the integers span a range larger than 65535, and it looks pretty insane. Nevertheless, I find it amusing that it works at all:

res: List[List[Int]] = List(List(0, 1, 2, 1), List(0, -1), List(0, 1, 2, 3, 2))

Answer 3

You can use foldLeft:

val delimiter = 0

val res = mySeq.foldLeft(Seq[Seq[Int]]()) {
  case (acc, `delimiter`) => acc :+ Seq(delimiter)
  case (acc, v) => acc.init :+ (acc.last :+ v)
}

NOTE: This assumes input necessarily starts with delimiter.