How to drop the first matching element in a Scala sequence

Summary: This blog post shows one way to drop/filter the first matching element from a Scala sequence (Seq, List, Vector, Array, etc.). I don’t claim that the algorithm is efficient, but it does work.

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 comes to mind looks like this:

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.

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 the first matching element from a Scala sequence (Seq, List, Vector, Array, etc.), I hope this example code is helpful.

Share it!

There’s just one person behind this website; if this article was helpful (or interesting), I’d appreciate it if you’d share it. Thanks, Al.

Permalink

// I like to propose another more functional approach
// good example to introduce scala's stable identifiers

def dropFirstMatch[T]( list : Seq[T] , `dropee` : T ) : Seq[T] = list.head match {
case `dropee` => list.tail
case other => Seq(other) ++ dropFirstMatch(list.tail,`dropee`)
}

// so this can be done more efficient, but for now ...
def dropLastMatch[T]( list : Seq[T] , `dropee` : T ) : Seq[T] =
dropFirstMatch(list.reverse, `dropee`).reverse

Add new comment

The content of this field is kept private and will not be shown publicly.

Anonymous format

  • Allowed HTML tags: <em> <strong> <cite> <code> <ul type> <ol start type> <li> <pre>
  • Lines and paragraphs break automatically.
By submitting this form, you accept the Mollom privacy policy.