How to remove leaf items in a Scala collection?

Question

Say I have a list that looks something like this:

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

What I would like to:

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

I delete all trailing zero. Is there a way, for example:

 list.trimRight(_ == 0) 

what will it do? I could write this from scratch, but it seems to me that this is something that would be with std collections?

I figured it out:

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

Is there a better approach?

Answer 1

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

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

since it should only refer to input once, and the intention is very clear.

If you want to know which one is most effective, you need to conduct a comparative analysis. The results (for your short list of tests) may surprise you!

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

There may be some modest differences between the machines, but basically this is the case when the short lists you like do not help. Things can change significantly with very long lists.

Here's a minimized version (but stack overflow on large lists):

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

Here's the user version (not completely general - 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 if you have no good reason. It is amazingly fast and surprisingly clear.

Answer 2

I think my answer list.take(list.lastIndexWhere(_ != 0)+1) is a way to do this.

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) 

Answer 4

There is no such method in Scala, and List very inefficient when changing it to "end". Prefer Vector .

This works well with List (my other suggestion was full of errors, and I deleted it):

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

Answer 5

You can traverse the list and buffer 0 until you find a non-0. If you find non-0, you will add a buffer to the result so far and continue. But if your list ends with 0, you delete the last buffer.

But - in the end, a reverse is still required.

 val xs = List(0,5,34,0,9,0,0,0) import annotation._ @tailrec def dropRight [T] (l: List[T], p: (T=>Boolean), carry: List[T]=List.empty, buf: List[T]=List.empty): List[T] = { if (l.isEmpty) carry.reverse else if (p (l.head)) dropRight (l.tail, p, l.head :: buf ::: carry, List.empty) else dropRight (l.tail, p, carry, l.head :: buf) } dropRight (xs, (x: Int) => x != 0) res122: List[Int] = List(0, 5, 34, 0, 9) 

It may be interesting if you are not interested in ordering at the end and can omit the “callback” call, but why then leave only the last Ts?

Benchmark:

• Source for reference
• Required Parent for Test

I increased the size further, but the pattern repeats.

updated: the dhg algorithm is included, which is quite effective.