I was doing a kata at Codewars and I came across surprising behavior of .rev()
when it's called twice in the same iterator chain.
The kata has you write a function that takes a slice of i32 and return a vector of every element that is larger than the sum of all the elements to its right, in the same order that they appear in the slice.
Here's the kata link, if you're interested:
Anyway, my solution was to get an iterator for the slice, reverse it, keep a running sum of elements seen so far, filter out elements that are not greater than the sum, reverse the iterator again , and collect it into a vector. But my first attempt didn't work:
fn array_leaders(arr: &[i32]) -> Vec<i32> {
let mut sum = 0;
arr.iter()
.cloned()
.rev()
.filter(|&n| {
sum += n;
n > sum - n
})
.rev()
.collect()
}
Surprisingly (to me anyway), this code behaves as if the iterator was never reversed at all! Commenting out both .rev()
calls doesn't change the output. The second call to .rev()
changes the order in which the elements are passed to the closure passed in to the prior call to .filter()
. That's the part that blows my mind.
Is this expected behavior? In the above code, that 2nd .rev()
doesn't just change the order of the iterator stream; it changes the content too, because the .filter()
closure uses an external mutable value. For example, when calling it with &[1, 2, 3, 4, 0]
, it's supposed to return a vec of [4], but instead returns [1, 2].
To get the correct behavior, I had to collect the results into a temporary vector and then create an iterator from that before calling .rev()
the second time:
fn array_leaders(arr: &[i32]) -> Vec<i32> {
let mut sum = 0;
arr.iter()
.cloned()
.rev()
.filter(|&n| {
sum += n;
n > sum - n
})
.collect::<Vec<_>>()
.into_iter()
.rev()
.collect()
}