Calling iterator .rev() twice gives unexpected behavior

#1

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()
}
#2

This can be a bit surprising, but yes, that's how rev works. This is the only way it could work if it is to be lazy.

1 Like
#3

In more detail, .rev() returns an iterator that wraps another iterator, and basically reverses the meanings of .next() and .next_back().

And in general, your chain of iterators are one iterator wrapping another. Try working through it this way:

let arr_iter = arr.iter();
let rev_1 = arr_iter.rev();
let rev_filter = rev_1.filter(|_| ...);
let rev_2 = rev_filter.rev();
// alt: let rev_2 = arr.iter().rev().filter(|_| ...).rev();

// What happens when we get the next element?
let foo_1 = rev_2.next();

// `rev_2.next()` wants to give you the _last_ element in its wrapped iter,
// so it calls `rev_filter.next_back()`
//
// `rev_filter.next_back()` wants to give you the last element in its wrapped iter,
// so it calls `rev_1.next_back()`
//
// `rev_1.next_back()` wants to give you the _first_ element in its wrapped iter,
// so it calls `arr_iter.next()`
//
// `arr_iter.next()` gives you the first element from `arr`.
// And that's why the elements are coming out in the forward order.

[Edit: fixed code typo]
1 Like
#4

For a slight improvement here, you could keep that first Vec and just reverse it in place.