Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

rust

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?

like image 552
mrbus2007 Avatar asked Aug 24 '18 21:08

mrbus2007


2 Answers

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);
}
like image 155
mcarton Avatar answered Oct 07 '22 06:10

mcarton


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]
like image 2
Yann Vernier Avatar answered Oct 07 '22 05:10

Yann Vernier