How do I remove trailing elements in a Scala collection?

Question

Let's say I have a list that looks something like this:

List(0,5,34,0,9,0,0,0)

What I'd like to end up with is:

List(0,5,34,0,9)

I'm removing all the trailing zero's. Is there a method, something like:

list.trimRight(_ == 0)

that will accomplish that? I could write it from scratch, but it seems to me that it's something that'd come with the std collections?

I came up with:

list.take(list.lastIndexWhere(_ != 0) + 1)

Is there a better approach?

Answer 1

If you want to know which is the most elegant, then I would say

list.reverse.dropWhile(_ == 0).reverse

since it only needs to refer to the input once, and the intent is very clear.

If you want to know which is the most efficient, you need to do some benchmarking. The results (for your short test list) might surprise you!

// Slowest
191 ns     dhg's EnhancedSeq
173 ns     user unknown's custom dropRight
 91 ns     andyczerwonka's take/lastIndexWhere
 85 ns     Rex's :\ (foldRight) -- see below
 60 ns     dhg / Daniel's reverse/dropWhile/reverse
 52 ns     Rex's customDropTrailingZeros -- see below
// Fastest

There may be some modest machine-to-machine differences, but basically this is a case where for short lists being fancy does not help you. Things may change considerably with very long lists.

Here's the fold version (but the stack overflows on large lists):

(list :\ list.take(0)){ (x,ys) => if (x==0 && ys.isEmpty) ys else x :: ys }

Here's the custom version (completely non-generic--good only for this specific task!):

@annotation.tailrec def customDropZeros(
  xs: List[Int],
  buffer: Array[Int] = new Array[Int](16),
  n: Int = 0
): List[Int] = {
  if (xs.isEmpty) {
    var ys = xs
    var m = n
    while (m>0 && buffer(m-1)==0) m -= 1
    var i = m-1
    while (i>=0) {
      ys = buffer(i) :: ys
      i -= 1
    }
    ys
  }
  else {
    val b2 = (
      if (n<buffer.length) buffer
      else java.util.Arrays.copyOf(buffer, buffer.length*2)
    )
    b2(n) = xs.head
    customDropZeros(xs.tail, b2, n+1)
  }
}

tl;dr

Use reverse dropWhile reverse unless you have good reason to otherwise. It's surprisingly fast and surprisingly clear.

Answer 2

I guess my answer of list.take(list.lastIndexWhere(_ != 0)+1) is the way to do it.

Answer 3

scala> val xs = List(0,5,34,0,9,0,0,0)
xs: List[Int] = List(0, 5, 34, 0, 9, 0, 0, 0)

scala> xs.reverse.dropWhile(_ == 0).reverse
res1: List[Int] = List(0, 5, 34, 0, 9)

EDIT:

Here's a one-pass (O(n)) way that adds an implicit dropWhileRight method to Seq

class EnhancedSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) {
  def dropRightWhile[That](p: A => Boolean)(implicit bf: CanBuildFrom[Repr, A, That]): That = {
    val b = bf(seq.asInstanceOf[Repr])

    val buffer = collection.mutable.Buffer[A]()
    for (x <- seq) {
      buffer += x
      if (!p(x)) {
        b ++= buffer
        buffer.clear()
      }
    }

    b.result
  }
}
implicit def enhanceSeq[A, Repr <: Seq[A]](seq: SeqLike[A, Repr]) = new EnhancedSeq(seq)

And you just use it like this:

scala> List(0,5,34,0,9,0,0,0).dropRightWhile(_ == 0)
res2: List[Int] = List(0, 5, 34, 0, 9)