CODEWITHSUNDEEP
rust
mrbus2007
mrbus2007

Reputation: 317

Why does a doubly-reversed iterator act as if it was never reversed?

I have an input vector which contains numbers. In an output vector, I need to get a sequence of partial products but in right-to-left order. The last element of the output must be equal to the last one in the input; the second-to-last element of the output must be a product of the last and second-to-last elements of input; and so on. For example, if the input vector is

let input = vec![2, 3, 4];

then I need the output to be [24, 12, 4].

My implementation takes an iterator over the input, reverses it, maps, reverses again and collects:

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let p: Vec<usize> = input
        .iter()
        .rev()
        .map(|v| {
            prod *= v;
            prod
        }).rev()
        .collect();
    println!("{:?}", p);
}

The result is [2, 6, 24], the same as if I delete both rev()s. The two rev()s do not solve the problem, they just "annihilate" each other.

Is this task solvable in "chain of calls" style, without using for?

Upvotes: 13

Views: 878

Answers (2)

Yann Vernier
Yann Vernier

Reputation: 15877

Your prod variable is carrying state across from one item to the next, which is not what a mapping does. Mappings operate on each element independently, which makes them easily parallelized and easier to reason about. The result you're asking for is to be precise a right scan (a reversed case of a prefix sum), but I'm not sure there are convenient methods to collect from the right (probably the easiest mutable way would be using VecDeque::push_front). This led me to perform the operation in two passes for my first version:

fn main() {
    let input: Vec<usize> = vec![2, 3, 4];
    let initprod = 1;
    let prev: Vec<usize> = input
        .iter()
        .rev()
        .scan(initprod, |prod, &v| {
            *prod *= v;
            Some(*prod)
        }).collect();
    let p: Vec<usize> = prev.into_iter().rev().collect();
    println!("{:?}", p);
}

Note that initprod is immutable; prod carries the state. Using into_iter also means prev is consumed. We could use vec.reverse as shown by mcarton, but then we need to have a mutable variable. Scans can be parallelized, but to a lesser degree than maps. See e.g. discussion on adding them to Rayon. One might also consider if a ExactSizeIterator should allow reverse collection into an ordinary vector, but the standard library scan method breaks the known size using Option (which by the next convention turns it into a take-while-scan).

Here's a fewer copy variant using a preallocated VecDeque to collect from the right. I used an extra scope to restrict the mutability. It also requires Rust 1.21 or later to use for_each. There's unnecessary overhead in tracking the number of items and ring buffer structure, but it's at least somewhat legible still. 

use std::collections::VecDeque;

fn main() {
    let input: Vec<usize> = vec![2,3,4];
    let p = {
        let mut pmut = VecDeque::with_capacity(input.len());
        let initprod = 1;
        input
            .iter()
            .rev()
            .scan(initprod, |prod, &v| {
                *prod *= v;
                Some(*prod)
            })
            .for_each(|v| { 
                pmut.push_front(v)
            });
        pmut
    };
    println!("{:?}", p);
}

Incidentally, following the old adage about Lisp programmers knowing the value of everything and the cost of nothing, here's a Haskell version I don't really know how inefficient it is:

scanr1 (*) [2, 3, 4]

Upvotes: 2

mcarton
mcarton

Reputation: 29981

This behavior is actually explicitly described in the documentation:

Notes about side effects

The map iterator implements DoubleEndedIterator, meaning that you can also map backwards:

[…]

But if your closure has state, iterating backwards may act in a way you do not expect. […]

A way to solve this would be by adding an intermediary collect to be sure that the second rev does not apply on the Map:

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let p: Vec<usize> = input
        .iter()
        .map(|v| {
            prod *= v;
            prod
        }).rev()
        .collect::<Vec<_>>()
        .into_iter()
        .rev()
        .collect();
    println!("{:?}", p);
}

But that requires an extra allocation. Another way would be to collect, and then reverse:

fn main() {
    let input = vec![2, 3, 4];
    let mut prod = 1;
    let mut p: Vec<usize> = input
        .iter()
        .rev()
        .map(|v| {
            prod *= v;
            prod
        }).collect();
    p.reverse();

    println!("{:?}", p);
}

Upvotes: 12

Related Questions