Scala: slice a list from the first non-zero element

Viewed 547

Suppose I have a list filled with zeroes

val a = List(0,0,0,0,2,4,0,6,0,7)

I want to slice away the zeroes preceding the first non-zero element and also return the index where the 1st non-zero element is present. Foe the above case I want an output:

output = List(2,4,0,6,0,7)
idx = 4

How do I do it?

7 Answers

First, you can use zipWithIndex to conveniently pair each element with its index. Then use dropWhile to return all of the preceding zero elements. From there, you'll have all of the remaining elements paired with their indices from the original List. You can unzip them. Since this may result in an empty list, the index you're looking for should be optional.

scala> val (remaining, indices) = a.zipWithIndex.dropWhile { case (a, i) => a == 0 }.unzip
remaining: List[Int] = List(2, 4, 0, 6, 0, 7) // <--- The list you want
indices: List[Int] = List(4, 5, 6, 7, 8, 9)

scala> val index = indices.headOption
index: Option[Int] = Some(4) // <--- the index of the first non-zero element

This is a use-case for span:

val a = List(0,0,0,0,2,4,0,6,0,7)

val (zeros, output) = a.span(_ == 0)
val idx = zeros.length

use dropWhile:

val output = a.dropWhile{ _ == 0 }
val idx = output.headOption
  .map(_ => a.length - output.length)
  .getOrElse(-1) // index starting from 0, -1 if not found

You can do it pretty clean with indexWhere:

val idx = a.indexWhere(_!=0)
val output = a.drop(idx)

Just another solution using foldLeft:

val (i, l) =
  a.foldLeft((None: Option[Int], List.empty: List[Int]))((b, n) => {
    if (n == 0 && b._2.isEmpty) (b._1.orElse(Some(0)).map(_ + 1), List.empty)
    else (b._1.orElse(Some(0)), b._2 :+ n)
  })
i: Option[Int] = Some(4)
l: List[Int] = List(2, 4, 0, 6, 0, 7)

Sightly modified from @bottaio answer, but returning an Option[Int] instead of a plain Int for the index.

def firstNonZero(l: List[Int]): (Option[Int], List[Int]) = {
  @annotation.tailrec
  def go(remaining: List[Int], idx: Int): (Int, List[Int]) =
    remaining match {
      case Nil     => idx -> Nil
      case 0 :: xs => go(remaining = xs, idx + 1)
      case xs      => idx -> xs
    }

  l match {
    case 0 :: xs =>
      val (idx, list) = go(remaining = xs, idx = 1)
      Some(idx) -> list

    case list =>
      None -> list
  }
}

Others have provided answers that requires multiple list traversals. You can write a recursive function to calculate that in a single pass:

def firstNonZero(l: List[Int]): (Int, List[Int]) = {
  @tailrec
  def go(l: List[Int], idx: Int): (Int, List[Int]) = l match {
    case Nil => (idx, Nil)
    case 0 :: xs => go(xs, idx + 1)
    case xs => (idx, xs)
  }

  go(l, 0)
}

what is also equivalent to

val (leadingZeros, rest) = a.span(_ == 0)
val (index, output) = (leadingZeros.length, rest)
Related