CODEWITHSUNDEEP
rustiteratorborrow-checker
Ruifeng Xie
Ruifeng Xie

Reputation: 906

Interleaved lifetime requirements for map/reduce

I have basically the following code:

iter.map(|x| t.f(x))
    .reduce(|x, y| t.g(x, y))
    .unwrap_or_default()

where f and g both borrow mutably from self.

The Rust borrow checker is not amused by this idea. Apparently, I cannot construct two closures mutably borrowing the same data t. But theoretically, the mutable borrow in f and g are both temporary, which means if this code did compile, during execution their borrows should be interleaved in time, and thus should not cause any actual problem.

The lifetime problem can be resolved by inlining f, g, map, and reduce (after which the invocations of f and g are indeed interleaved in time, and the borrow checker is satisfied), but then the simplicity in program structure is totally ruined. Another way to solve this would be to wrap the mutably borrowed data by a RefCell, but I suspect it will introduce runtime penalty.

Is there any clever way to satisfy the borrow checker without compromising clarity?

I tried to partially inline reduce and map. The following does not type check (indeed it should not, since here f is repeatedly called on the first argument of g, while in the original code f is only invoked once on every item in iter):

iter.reduce(|x, y| t.g(t.f(x), t.f(y)))
    .unwrap_or_default()

Use a fold should solve this, see the following:

iter.fold(None, |res, y| Some(match res {
    None => t.f(y),
    Some(res) => t.g(res, t.f(y)),
})).unwrap_or_default()

But this code is inefficient (and not as readable): it will match on each iteration, while theoretically only one match is necessary.

If we use the trick in reduce, the code becomes tedious:

(|| {
    let first = iter.next()?;
    Some(iter.fold(t.f(first), |res, y| t.g(res, t.f(y))))
})().unwrap_or_default()

Another inconvenience is that iter is mentioned twice here, so I am forced to store this iterator in some variable, instead of directly use some expressions returning an iterator.

Update: MRE provided here in Compiler Explorer

Upvotes: 2

Views: 148

Answers (2)

Ruifeng Xie
Ruifeng Xie

Reputation: 906

To summarize:

  • we don't (yet?) have good solution to properly reuse map and reduce;
  • fold with Default::default() is not semantically equivalent in that it call t.g once more than map followed by reduce;
  • fold with Option is not as efficient;

My final solution is to factor out the reduce_map logic to a function:

pub trait IterHelper: Iterator {
    /// `Iterator::map` followed by `Iterator::reduce`, with lifetime issues properly handled.
    fn reduce_map<V, A>(mut self, visitor: &mut V,
                        f: impl Fn(&mut V, Self::Item) -> A,
                        g: impl Fn(&mut V, A, A) -> A) -> Option<A>
        where Self: Sized, V: ?Sized {
        let first = f(visitor, self.next()?);
        Some(self.fold(first, |res, x| {
            let a = f(visitor, x);
            g(visitor, res, a)
        }))
    }
}

impl<I: Iterator> IterHelper for I {}

Upvotes: 0

Alexey S. Larionov
Alexey S. Larionov

Reputation: 7937

Since you use unwrap_or_default() at the end, it means that a plain .fold can be a bit shorter

let result = v.iter()
    .fold(Default::default(), 
        |res, x| { let tfx = t.f(x); t.g(res, tfx) });

Unfortunately this even shorter version didn't work due to double borrow

let result = v.iter()
    .fold(Default::default(), 
        |res, x| t.g(res, t.f(x)));

Playground

Upvotes: 0

Related Questions