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. (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:

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

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

`dropLastMatch` opens the way to some optimisation. The described algorithm performs:

  1. A first pass: To locate the element index.
  2. 2) Then a second: To split the sequence and then ...
  3. 3) A third pass: Over the left sequence of the split (a) to concatenate (b)

In the case of dropping the last match, you can use `foldRighth` to accumulate the result in a single pass, e.g:


def deleteLast[T](s: Seq[T], target: T): Seq[T] =
(s :\ (Seq.empty[T], false)) {
case (v, (acc, del)) if(del || v != target) =>
(v +: acc, del)
case (_, (acc, _)) =>
acc -> true
}._1

As `foldRight` will iterate from right to left, the O(1) sequence builder element +: s will build the new sequence in the right order, discarding or keeping elements as they are the first match (from right, that is the last) or not.

Congrats for this great blog, I love it! It's a kind of "Encyclopedia galactica" for Scala.

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.