The first find_max in this repository did not compile. The error was expected &i32, found Option<&i32>, and the seed was the whole problem.
The broken one, from a commit called WIP:
pub fn find_max(nums: Vec<i32>) -> i32 {
let mut max = nums.first();
for num in nums.iter() {
if num > max {
max = num;
}
}
max
}
nums.first() returns Option<&i32>, and num is &i32. Comparing a &i32 against an Option<&i32> is not a thing, and the compiler says so precisely:
error[E0308]: mismatched types
--> src/main.rs:11:22
|
11 | if num > max {
| ^^^ expected `&i32`, found `Option<&i32>`
There is no PartialOrd between a reference and an Option. The type error is the compiler refusing to let the seed be two different things at once.
What shipped, fourteen minutes later:
pub fn find_max(nums: Vec<i32>) -> i32 {
// iterative
// rusty
let mut max = i32::MIN;
nums.iter().copied().for_each(|num| {
if num > max {
max = num
}
});
max
}
Two changes, and both of them are about the seed.
A seed nothing can beat
The seed is the identity element for max over i32. It is the one value that no element of the array can beat, so folding over the array with it as the starting accumulator always produces the true maximum. i32::MAX would be the identity for min. Pick the wrong one and the answer is wrong in a way that depends on the data.
I changed the seed to 0 and ran the repository’s own test suite:
test result: FAILED. 0 passed; 1 failed
---- tests::find_max_test stdout ----
thread 'main' panicked at src/main.rs:23:9:
assertion `left == right` failed
left: 0
right: -1
One assertion out of three. [1, 5, 3, 9, 2] still returns 9, and [42] still returns 42, because with a seed of 0 the fold still finds the maximum whenever the maximum is positive. Only the all-negative case breaks.
That is the case the test suite happens to contain:
assert_eq!(Solution::find_max([-1, -5, -3].to_vec()), -1);
This one line is the only reason the seed is correct. If the repository had only the positive examples, the seed could be 0 and every test would still be green, and the solution would be wrong for every all-negative array it ever saw. The other two assertions are decoration.
I do not think this is a coincidence of the problem statement. The problem’s own second example is nums = [-1, -5, -3], output -1. If the test had been written from the problem’s first example instead, the bug would have shipped.
Getting the value out of the reference
The other thing in that line is nums.iter().copied().
nums.iter() yields &i32. The comparison num > max needs an i32 on the right, and max is an i32. Comparing &i32 with i32 does not typecheck either:
error[E0308]: mismatched types
--> src/main.rs:13:22
|
13 | if num > max {
| ^^^ expected `&i32`, found `i32`
.copied() is Iterator::copied, which converts an iterator of &T into an iterator of T where T: Copy. i32 is Copy, so the borrow is replaced by a copy of the value. It is the same reason you write *num in the find_min solution next door. The difference in style is that find_max uses .copied() and find_min uses *num inside the closure. Both are moving the i32 out of the &i32.
for_each rather than a for loop is a matter of taste. for_each takes an FnMut, so the closure can mutate the max it captured, and I confirmed that mutating a captured variable works.
The seed leaks into the answer
There is one behavior here I want to name, because it is not a bug in the constraints but it is a real property of the design. The function returns i32 and has no way to say “there was nothing here.”
find_max([]) = -2147483648
For an empty array the function returns the seed, which is i32::MIN. There is no way for a caller to distinguish “the array was empty” from “the array contained only i32::MIN.” The constraint 1 <= nums.len() rules this out, so it does not matter here, but a find_max that took a slice of unknown provenance would need a different shape.
The stdlib version of this problem does not have that problem, because it returns Option:
nums.iter().max()
and None is exactly the right answer for an empty slice. I chose i32::MIN as the seed and the return type of i32 forced the other end of the same choice. The seed and the return type are one decision, and the type system made me make it explicitly.
The compiler rejected my first attempt because it tried to hide the decision behind an Option. The second attempt makes it in the open, where the test suite can check it.
Next time I write one of these, the seed and the return type get chosen together, before the body. That decision is the whole design, and it costs nothing to make it early.
Next: I Wrote the Fold by Hand