Finding the First Element Matching a Condition in a Collection

1. Introduction

In this tutorial, we’ll explore two ways to solve a simple problem – given a sequential collection, how do we find the first element that satisfies a given condition?

2. Solution

We’ll see two ways to solve the problem to understand how different criteria can lead to different solutions.

2.1. Using find()

Our first approach is very practical and uses the resources that the powerful collections library from Scala gives us out-of-the-box. It doesn’t teach us much about algorithms but helps us get the job done effectively.

When we explore the Scala documentation for collections, we’ll find a method that does exactly what we need with the following signature:

def find(p: (A) => Boolean): Option[A]

The search might fail to find a result that satisfies the given predicate. Recognizing that possibility, the method returns an Option[A] instead of a simple A.

Here’s how we can use it to find an existing element:

// say that we have a list of integers:
val integers = 2 :: 4 :: 6 :: 7 :: 8 :: Nil

// and we are interested in the first odd integer:
val predicate = (n: Int) => n % 2 == 1

// let's find it!
val maybeOddInt = integers.find(predicate)

// did we get it?
assertResult(Some(7))(maybeOddInt)

2.2. Using Recursion

Our second approach uses a tail recursive function, and an implicit value class:

object Finder {
  implicit class Wrapper[T](val sequence: Seq[T]) extends AnyVal {
    @tailrec
    final def findMatch(condition: T => Boolean): Option[T] = {
      if (sequence.isEmpty) None
      else if (condition(sequence.head)) Some(sequence.head)
      else sequence.tail.findMatch(condition)
    }
  }
}

Here are some elements of this snippet that are worth noticing:

• Although this is a simple algorithm, we have been careful to make it efficient. We want to ensure it doesn’t provoke memory exhaustion with big collections! So we have marked it with the tail recursion annotation and implemented it that way.
• The code takes the form of a method in an implicit value class (that implicit class … extends AnyVal near the top), which makes the life of the users of our method much easier, as we are effectively extending the collection’s functionality.
• The value class takes a type parameter T to apply our method to collections of any type.
• The value class takes as a parameter a Seq[T], the most basic type for sequences of things. Finding the first element that matches a condition only makes sense in sequences.
• The method that does the heavy lifting returns an Option[T]. That’s because no element of the collection may satisfy the predicate!

3. Testing

We can test the functionality of our findMatch() method, using the powerful ScalaTest framework:

class FinderSpec extends AnyWordSpec {
  import Finder._

  "A finder" should {
    "find nothing in an empty collection" in {
      val collection = Vector[Int]()
      val expected = None
      val actual = collection.findMatch(_ > 0)
      assertResult(expected)(actual)
    }
    "find nothing if the element is not there" in {
      val collection = 2 :: 4 :: 6 :: 8 :: Nil
      val expected = None
      val actual = collection.findMatch(_ > 8)
      assertResult(expected)(actual)
    }
    "find the first element that matches" in {
      val collection =
        ('a' -> 0) :: ('b' -> 1) :: ('c' -> 2) :: ('d' -> 3) :: Nil
      val expected = 'b'
      val actual = collection.findMatch(pair => pair._2 > 0).get._1
      assertResult(expected)(actual)
    }
  }
}

4. Conclusion

In this article, we learned two ways to find the first element of a sequential collection that matches a specific predicate. In general, we should prefer using the collections library because the code is very performant and thoroughly tested.

Nonetheless, by providing our own implementation, we can learn or refresh interesting, idiomatic, and efficient patterns in our coding. Also, it can be a stepping stone to solving variations of the problem, like finding the nth element that satisfies the condition.