Removing from the head of a mutable list

Scala Improvement Process
1

I was surprised that it seems there’s no way to remove the first element of a mutable.ListBuffer. In my experience, that is a very useful operation we can use to build many algorithms. For example, I often use it to process work lists (e.g., a visiting a graph).

def process(work: mutable.ListBuffer[Item]): Unit = 
  work.popFirst() match {
    case Some(a) => {
      doSomething(a, work) // `doSomething` may add new work items
      process(work)
    }
    case None => ()
  }

Here’s a possible implementation of popFirst. Note that a similar method makes sense on many other data structures.

extension [T](self: mutable.ListBuffer[T]) {

  /// If `self` is not empty, removes and returns its first element. Otherwise, returns `None`.
  ///
  /// - Complexity: O(1)
  def popFirst(): Option[T] = {
    if (self.isEmpty) { None }
    else { Some((self.head, self.remove(0))(0)) }
  }

}

Am I missing an obviously better way to implement the patterns enabled by popFirst in Scala or is it an operation we may consider adding to the standard library when we’ll unfreeze its API?

2

Instead of ListBuffer maybe consider using a Stack?

If you prefer to use a linked-list style structure instead of an array-backed structure, alternately consider just using an immutable List since pushing/popping are O(1). You can keep the List in a var that can be updated.

In my experience the main usecase for ListBuffer is to build up a collection via appends and then efficiently convert to a List by “freezing” the current state.

2 Likes
3

I would call it behead.

The situation is egregious because ListBuffer doesn’t even override head (which goes through its iterator).

It also occurs to me that the natural (or naive) thing would be to pattern match on the underlying list. (The other comment suggests just consuming the list.)

Failing that, the next impulse is to match with an extractor that removes n prefix elements. (remove that takes a count doesn’t return the elements.)

I agree with the comment, that ListBuffer exists because building a list in reverse is a nuisance. However, in the spirit of whether to use ArrayBuffer or ArrayBuilder, I think it should be natural to use ListBuffer as a Buffer. We should probably have a ListBuilder for the simple use case.