How to drop the first matching element in a Scala sequence

Summary: This blog post shows one possible way to drop/filter the first matching element from an immutable Scala sequence (Seq, List, Vector, etc.). I don’t claim that the algorithm is efficient, but it does work. (See the Comments section after the article for other algorithms.)

Background

While creating some Scala test code earlier today I had an immutable list of toppings for a pizza, and I got into a situation where I wanted to remove the first instance of a topping.

For example, if a customer said they wanted a pizza with black olives and double pepperoni, one way to represent that is like this:

val toppings = Seq("black olives", "pepperoni", "pepperoni")

Obviously it’s not a good idea to represent toppings as strings, but I’m trying to keep this blog post simple.

The problem comes up when a customer changes their mind and tells you that they don’t want “double pepperoni,” they just want “single pepperoni.” Because I have the toppings modeled as an immutable sequence, I need a way to filter/drop one of the “pepperoni” entries, but not both.

Dropping the first matching element from a sequence

In short what I wanted was something like this:

val newToppingList = toppings.dropFirstMatch("pepperoni")

Unfortunately there are no methods to do this in the Scala sequential collections — Seq, List, Vector, etc. — so I wrote my own function, whose invocation looks like this:

val newToppingList = dropFirstMatch(toppings, "pepperoni")

An algorithm to drop the first matching element

There are many ways to implement a “drop the first matching element” algorithm, but the first one that came to mind was this:

// first attempt at an algorithm
def dropFirstMatch[A](ls: Seq[A], value: A): Seq[A] = {
    val index = ls.indexOf(value)  //index is -1 if there is no match
    if (index < 0) {
        ls
    } else if (index == 0) {
        ls.tail
    } else {
        // splitAt keeps the matching element in the second group
        val (a, b) = ls.splitAt(index)
        a ++ b.tail
    }
}

Hopefully that algorithm is easy to read, but here’s a quick description of it:

• I look for the index of the first match in the sequence.
• If there is no match I just return the original list.
• If the match is the 0th element in the sequence I return the tail of the sequence.
• If the match is in any other position I split the original sequence into two sequences, then put the sequences back together while removing the matching element from the sequence named b.

(Caution: I don’t know how efficient this approach is. I’m working with very small lists where performance isn’t a great concern, and it’s definitely something I haven’t tested.)

Another algorithm

As a quick update, I came back to this today and thought about another algorithm to drop the first matching element in a list/sequence, and this also works:

// second algorithm (which i like better)
def dropFirstMatch[A](xs: Seq[A], value: A): Seq[A] =
    val idx = xs.indexOf(value)
    for
        (x, i) <- xs.zipWithIndex
        if i != idx
    yield
        x

That code is written using Scala 3, but more importantly, I think this is easier to read than my initial algorithm.

Example code

I tested this dropFirstMatch function with this code:

val ls = Seq(1, 2, 3, 1, 2, 3, 4)

val a = dropFirstMatch(ls, 1); println(a)
val b = dropFirstMatch(ls, 2); println(b)
val c = dropFirstMatch(ls, 3); println(c)
val d = dropFirstMatch(ls, 4); println(d)
val e = dropFirstMatch(ls, 7); println(e)  //test what happens when there is no match

That code results in the following output:

List(2, 3, 1, 2, 3, 4)
List(1, 3, 1, 2, 3, 4)
List(1, 2, 1, 2, 3, 4)
List(1, 2, 3, 1, 2, 3)
List(1, 2, 3, 1, 2, 3, 4)

Note: I really want to drop the last matching element

I wrote this blog post saying that I wanted to drop the first matching element in a sequence, but in my pizza application I really want to drop the last element. That’s because if the customer says they want “Pepperoni, olives, onions, no, make that double pepperoni,” then they later say, “Make that just single pepperoni,” I want the order to read “Pepperoni, olives, onions,” not “olives, onions, pepperoni.”

As a result of this, I really want a dropLastMatch method, not a dropFirstMatch method. I thought I’d share that both for completeness, and to let you know it was a consideration in the algorithm I wrote. If you know the Scala Seq methods, you know this is a simple change to the algorithm shown.

If you like thought exercises, what other algorithms can you come up with to solve this problem (either dropping the first matching element, last matching element, or both)?

Summary

In summary, if you wanted to see one way to drop only one matching element from a Scala sequence (Seq, List, Vector, Array, etc.), I hope this example code is helpful.