The find Algorithm
Parameterizing an algorithm with an action lets the caller decide what is tested or done for each element. The algorithm controls the traversal; the caller controls the question.
Predicting the First Match
Imagine a list of names paired with scores, visited in a fixed order. You want the first entry whose score is larger than 42. Before reading on, try to work out which entry a search should return. The answer depends on one rule that this article builds up piece by piece: a find-style search stops at the first element that meets the requirement, not at the best element overall.
What do you think happens?
The entries, in order, are ana with 17, ben with 58, and cy with 90. Which entry does a find-style search return when the requirement is that the score is greater than 42?
Reveal answer
ben, with the score 58
The search checks ana first. Its score of 17 does not meet the requirement, so the search moves on. Ben's score of 58 does meet it, so the search stops there and returns ben. Cy also meets the requirement, but it is never reached because the search has already stopped.
Why a Fixed Search Falls Short
Many algorithms in the standard library come with their behavior fixed in advance. You call them, and they do one specific thing to each element of a sequence. That is convenient when the task matches exactly what the algorithm was designed for. Real searches rarely stay that simple, however. A plain search for one particular value asks whether each element equals that value. It cannot answer a question such as whether a score is larger than 42.
The way out is to stop building the test into the algorithm. Instead, you hand the test to the algorithm as an argument. The source describes this as making the action a parameter. Once the action is a parameter, the algorithm only has to supply the sequence and the order in which its elements are visited. The caller supplies the question asked of each element. The same algorithm can then be reused for many different purposes.
Parameterizing an algorithm with an action lets the caller decide what is tested or done for each element. The algorithm controls the traversal; the caller controls the question.
Predicates as Requirements
A predicate is a requirement or condition that an element of a sequence must fulfill.
The word requirement is the key to the idea. A predicate is not a value you search for. It is a question you ask about a value, such as whether it is larger than 42. The answer decides whether that element is the one you want. A find-style algorithm uses the predicate in place of a fixed value. Where a plain search asks whether an element equals a given value, the predicate version asks whether an element meets the stated condition.
| Aspect | Search for a fixed value | Search with a predicate |
|---|---|---|
| What is supplied | One value to match | A requirement to test |
| Question asked of each element | Does this element equal the value? | Does this element meet the condition? |
| Typical example | Is the score 42? | Is the score greater than 42? |
| Which elements can match | Only one exact value | Any element that satisfies the condition |
A predicate is more general than a fixed value because one requirement can be satisfied by many different elements.
Maps as Sequences of Pairs
The source uses a map as its example, and it is a good one because it shows why a predicate is needed at all. A map lets you reach its elements as a sequence of (key, value) pairs. So a map from strings to integers can be treated as a sequence of pairs, each with a string key and an integer value. The goal is to search that sequence for a pair whose integer is greater than 42.
Each element in the diagram is one key-value pair. The key labels the pair, but it plays no part in the test. The predicate inspects only the integer value, because the requirement concerns the score. This separation is the reason the predicate has to be written with care: it must read the correct part of each element.
Tracing the Search One Pair at a Time
Now trace the search itself. The find-style algorithm visits the pairs in order and applies the predicate to each one. It stops as soon as the predicate returns true for an element, and it returns that element. The diagram below follows the three-pair map from the opening prediction.
Tracing find with the requirement greater than 42
Pairs in order: ana 17, ben 58, cy 90. Find the first pair whose integer is greater than 42.
- 1Visit the first pair
The search starts with ana. The predicate reads the integer 17 and asks whether 17 is greater than 42. The answer is false, so ana is not the one wanted and the search moves on.
- 2Visit the second pair
The search reaches ben. The predicate reads 58 and asks whether 58 is greater than 42. The answer is true, so ben fulfills the requirement.
- 3Stop the search
Because the predicate returned true, the search stops. Cy is never tested, even though its score of 90 would also satisfy the requirement.
The search returns the pair ben with the integer 58, the first element that fulfills the requirement.
Writing the Predicate as a Lambda
A predicate has to be given to the algorithm somehow. One option is to define a separate named function that answers the question and pass its name. A lambda expression offers a shorter route. You write the requirement directly at the place where the algorithm is called, without giving it a separate name. The lambda is the predicate, and its body is the question the predicate asks of each element.
For the map search, the lambda receives one pair as its argument. Its body looks at the integer part of that pair and produces a yes-or-no answer: true when the integer is greater than 42, and false otherwise. Because the body only reads the pair and answers the question, it fits naturally into a single expression placed right beside the search. The expression below is written in generic pseudo-notation to show the parts, not in any particular language's exact syntax.
The lambda's parameter stands for the element being tested, its body states the requirement, and its return value is the yes-or-no answer that tells the search whether to stop.
Changing the Requirement Without Changing the Algorithm
The payoff of passing the predicate as an argument is that the requirement can change while the algorithm stays the same. Suppose the same map is searched again, but now for the first pair whose integer is greater than 80. The traversal is identical: the search still visits ana, then ben, then cy, and it still stops at the first match. Only the predicate has changed.
requirement: value greater than 42 visit ana (17): false visit ben (58): true, stop result: ben
The requirement is greater than 42, so ben is the first match.
requirement: value greater than 80 visit ana (17): false visit ben (58): false visit cy (90): true, stop result: cy
The requirement is greater than 80, so ben no longer qualifies and cy becomes the first match.
What stays fixed is the sequence and the order of traversal, which the algorithm owns. What varies is the question asked of each element, which the caller supplies. This split is exactly what the source means when it says that changing the requirement changes the result without touching the algorithm.
Mistakes Beginners Make With Predicates
Common mistake Treating the predicate as the value to search for
What it looks likePassing 42 and expecting the search to find the pair whose integer is greater than 42.
Why it failsA predicate is a question about each element, not a fixed value. A fixed value only matches elements that are exactly equal to it.
Do this insteadWrite the requirement as a condition, such as the integer is greater than 42, and let the predicate return true or false for each element.
Common mistake Testing the key when the requirement concerns the value
What it looks likeA lambda that checks whether the key ben is greater than 42.
Why it failsThe key does not matter for this requirement. The integer part of each pair is what the test must read.
Do this insteadRead the value part of the pair in the predicate body.
Common mistake Expecting the search to return the best element
What it looks likeAssuming the search returns cy with 90 because it is the largest score.
Why it failsThe search stops at the first element that fulfills the requirement, so later elements are never examined.
Do this insteadIf the largest value is needed, a different question must be asked, and the search rules must be chosen to match it.
Common mistake Forgetting that the predicate must return a yes-or-no answer for every element it is given
Trying a Predicate Yourself
The map has the pairs ana with 17, ben with 58, cy with 90, and dee with 44, visited in that order. Write the predicate, in words or in the lambda form shown earlier, that a find-style search would use to locate the first pair whose integer is greater than 42. Then state which pair the search returns and which pairs it never tests.
Hints
- Identify which part of each pair the requirement reads.
- Trace the pairs in order and stop at the first one whose integer is greater than 42.
- Remember that the pairs after the match are never tested.
Key Takeaways From the Search
- 1A predicate is a requirement or condition that an element of a sequence must fulfill, and it answers a yes-or-no question about each element.
- 2Making the action a parameter lets the caller decide what is tested, while the algorithm keeps control of the sequence and the order of traversal.
- 3A find-style search applies the predicate to each element in order and returns the first element that fulfills it.
- 4A lambda expression lets you write the predicate directly where the search is called, and for a map the predicate reads the value part of each key-value pair.
At a glance
- A predicate is a requirement or condition that an element of a sequence must fulfill.
- Passing the action as a parameter lets the caller choose the question asked of each element while the algorithm controls traversal.
- A find-style search stops at and returns the first element that fulfills the predicate.
- A lambda expression lets you write a predicate in place, and over a map it reads the value of each key-value pair.