Is it possible to use fold in Rust if the accumulator is neither copy type nor mutable

Question

I am trying to make a fold work and encountered with lifetime issues. Here is the simplified version of my code:

struct A {
  v: i32,
}
let v = vec![A { v: 1 }, A { v: 2 }, A { v: 3 }];
let max = v.iter().fold(None, |res: Option<A>, &item| { match res {
    Some(a) => if a.v >= item.v { Some(a) } else { Some(item) },
    None => Some(item)
}});

This results in error[E0507]: cannot move out of borrowed content.

If I change the closure to |res: Option<A>, ref item| ... as adviced by the previous error, I get a type mismatch at Some(item) and solving that dereference gets back to the original error.

I tried to have a reference in the option but then I get lifetime issues:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
 --> <anon>:6:67
  |
6 |   let maxV = v.iter().fold(None, |res: Option<&A>, &item| { match res {
  |                                                                   ^^^
  |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the body at 6:58...
 --> <anon>:6:59
  |
6 |     let maxV = v.iter().fold(None, |res: Option<&A>, &item| { match res {
  |  ___________________________________________________________^ starting here...
7 | |       Some(a) => if a.v >= item.v { Some(a) } else { Some(&item) },
8 | |       None => Some(&item)
9 | |   }});
  | |____^ ...ending here
note: ...so that types are compatible (expected std::option::Option<&main::A>, found std::option::Option<&main::A>)
 --> <anon>:6:67
  |
6 |   let maxV = v.iter().fold(None, |res: Option<&A>, &item| { match res {
  |                                                                   ^^^
note: but, the lifetime must be valid for the method call at 6:13...
 --> <anon>:6:14
  |
6 |     let maxV = v.iter().fold(None, |res: Option<&A>, &item| { match res {
  |  ______________^ starting here...
7 | |       Some(a) => if a.v >= item.v { Some(a) } else { Some(&item) },
8 | |       None => Some(&item)
9 | |   }});
  | |_____^ ...ending here
note: ...so that argument is valid for the call
 --> <anon>:6:28
  |
6 |   let maxV = v.iter().fold(None, |res: Option<&A>, &item| { match res {
  |                            ^^^^

The first version works if I make A a copy type by adding #[derive (Copy, Clone)] but that is not always an option.

I tried to search for fold examples in rust, but I either found ones where the accumulator is a copy type (i32 sums implemented with fold) or where the accumulator is a container and the fold is manipulating the content (extending a vector or similar).

I also found an example that folds into an Option but that does not match on the current value of the accumulator.

I can do it with a for loop but would prefer the fold syntax.

Answer 1

There are several bugs in the compiler regarding the inference of lifetime parameters on closure parameters; the one you've encountered here has been reported as issue 36867. In res: Option<&A>, the lifetime inferred for &A is wrong, and it seems to be caused by the return type (which is Option<&A>) also having a lifetime parameter. The workaround is to let the compiler infer the whole type, which works fine, and instead either give a type hint on the initial accumulator value (None):

#[derive(Debug)]
struct A {
    v: i32,
}

fn main() {
    let v = vec![A { v: 1 }, A { v: 2 }, A { v: 3 }];
    let max = v.iter().fold(None::<&A>, |res, item| { match res {
        Some(a) => if a.v >= item.v { Some(a) } else { Some(item) },
        None => Some(item)
    }});
    println!("{:?}", max);
}

or on the max variable:

fn main() {
    let v = vec![A { v: 1 }, A { v: 2 }, A { v: 3 }];
    let max: Option<&A> = v.iter().fold(None, |res, item| { match res {
        Some(a) => if a.v >= item.v { Some(a) } else { Some(item) },
        None => Some(item)
    }});
    println!("{:?}", max);
}

Bonus: For the particular problem of finding the maximum, you can also use Iterator::max_by_key. No annotations required!

fn main() {
    let v = vec![A { v: 1 }, A { v: 2 }, A { v: 3 }];
    let max = v.iter().max_by_key(|item| item.v);
    println!("{:?}", max);
}

Answer 2

The iterator you get from Vec::iter() produces immutable borrowed references (&A in this case) to the elements in the vector; the vector will be unchanged afterwards.

As a reminder, by default in Rust using a value moves it out, leaving the orignal unusable; you can only do this if you own the item, i.e. you can't move out of a borrowed reference. The exception to this is with types which are Copy, which means that they're "simple enough" that a raw memory copy is ok and doesn't invalidate the original object.

So for any type which is not Copy, you can't assign directly from an immutable reference.

There are several options.

First, if you can implement or derive Clone (which means you provide a method which can copy the object, possibly doing more than just a raw copy) without Copy, you can do explicitly clone:

let max = v.iter().fold(None, |res: Option<A>, item| match res {
    Some(a) => if a.v >= item.v { Some(a) } else { Some(item.clone()) },
    None => Some(item.clone()),
});

You could manually construct the new items inline (Some(A { v: item.v })), but if you're doing that you may as well derive or implement Clone.

If you can consume (i.e. destroy) your vector of items to get the result, then you can move after all by calling the into_iter() method instead of iter(); the iterator in that case owns the items (the original owner, the Vec, is consumed in the process) so you can move them:

let max = v.into_iter().fold(None, |res: Option<A>, item| match res {
    Some(a) => if a.v >= item.v { Some(a) } else { Some(item) },
    None => Some(item),
});

Moving works fine there, but the Vec no longer exists.

Either way, you either need to make a copy (via Copy, Clone, or something more manual) or move - it's up to your application which is more appropriate.