Finding the First List Element That Passes a Test (Perl Cookbook, 2nd Edition)

## 4.13. Finding the First List Element That Passes a Test

### 4.13.1. Problem

You want the first element in the list (or its index) that passes a test. Alternatively, you want to know whether any element passes the test. The test can be simple identity ("Is this element in the list?")[7] or more complex ("I have a list of Employee objects, sorted from highest salary to lowest. Which manager has the highest salary?"). Simple cases normally require only the value of the element, but when the array itself will be altered, you probably need to know the index number of the first matching element.

> [7]But why didn't you use a hash then?

### 4.13.2. Solution

To find a matching value, use `foreach` to loop over every element, and call `last` as soon as you find a match:

>     my ($match, $found, $item);
>     foreach $item (@array) {
>         if (CRITERION) {
>             $match = $item;  # must save
>             $found = 1;
>             last;
>         }
>     }
>     if ($found) {
>         ## do something with $match
>     } else {
>         ## unfound
>     }

To find a matching index, use `for` to loop a variable over every array index, and call `last` as soon as you find a match:

>     my ($i, $match_idx);
>     for ($i = 0; $i < @array; $i++) {
>         if (CRITERION) {
>             $match_idx = $i;    # save the index
>             last;
>         }
>     }

>     if (defined $match_idx) {
>         ## found in $array[$match_idx]
>     } else {
>         ## unfound
>     }

The List::Util module, shipped standard with Perl as of v5.8 but available on CPAN for earlier versions, provides an even easier approach:

>     use List::Util qw(first);
>     $match = first { CRITERION } @list

### 4.13.3. Discussion

Lacking (until recently) a built-in mechanism to do this, we must write our own code to go through the list and test each element. We use `foreach` and `for`, and call `last` to ensure that we stop as soon as we find a match. Before we use `last` to stop looking, though, we save the value or index.

A common approach is to try to use `grep` here. But `grep` always tests all elements and finds all matches, so it's inefficient if you want only the first match. However, `grep` might still be faster. That's because there will be less source code if you use `grep` rather than writing your own loop. That means fewer internal Perl operations, and it is these that in practice often dominate runtimes.

Beyond a certain size of your data set, a loop that terminates early will still be faster—assuming it has the chance to do so. Empirical evidence suggests that `for` will be faster as long as you can exit before the first two-thirds of the list has been examined. It's worthwhile to know how to do that.

We have to set `$match` when we want the value of the first matching element. We can't just test `$item` at the end of the loop, because `foreach` automatically `local` izes the iterator variable and thereby prevents us from accessing the final loop value after the loop ends. See Recipe 4.5.

Here's an example. Assume that `@all_emps` holds a list of Employee objects, sorted in descending order by salary. We wish to find the highest paid engineer, who will be the first engineer in the array. We only want to print the engineer's name, so we want the value, not the index.

>     foreach $employee (@all_emps) {
>         if ( $employee->category( ) eq 'engineer' ) {
>             $top_engr = $employee;
>             last;
>         }
>     }
>     print "Highest paid engineer is: ", $highest_engineer->name( ), "\n";

When we're searching and want only the index, we can save some code by remembering that `$i` will not be an acceptable array index if we don't find a match. This mainly saves us code space, as not doing an assignment doesn't really win much compared to the time spent testing list elements. It's more obscure, because it tests `if ($i < @ARRAY)` to check whether we found a match, instead of the more obvious `defined` test in the previous solution.

>     for ($i = 0; $i < @ARRAY; $i++) {
>         last if CRITERION;
>     }
>     if ($i < @ARRAY) {
>         ## found and $i is the index
>     } else {
>         ## not found
>     }

The `first` function from List::Util encapsulates the logic from an entire loop into a convenient, easy-to-use function. It acts just like a short-circuiting form of the built-in `grep` function that stops as soon as a match is found. While running, each list element is in a localized `$_` variable. For example:

>     $first_odd = first { $_ % 2 =  = 1 } @ARRAY;

Or rewriting the previous employee loop:

>     $top_engr = first { $_->category( ) eq 'engineer' } @all_emps;

### 4.13.4. See Also

The "For Loops," "Foreach Loops," and "Loop Control" sections of perlsyn(1) and Chapter 4 of Programming Perl; the `grep` function in perlfunc(1) and Chapter 29 of Programming Perl

Copyright © 2003 O'Reilly & Associates. All rights reserved.