How do I bound a generic type with a trait that requires a lifetime parameter if I create the reference inside the function?

Question

I want to implement a generic fibonacci function that works with any type implementing Zero, One, and AddAssign. I first implemented a version that works fine, but is specialized for num::BigUint (see on play.rust-lang.org). I than came up with the following generic implementation (see on play.rust-lang.org):

extern crate num;

use num::{One, Zero};
use std::mem::swap;
use std::ops::AddAssign;

fn fib<T: Zero + One + AddAssign<&T>>(n: usize) -> T {
    let mut f0 = Zero::zero();
    let mut f1 = One::one();
    for _ in 0..n {
        f0 += &f1;
        swap(&mut f0, &mut f1);
    }
    f0
}

This doesn't compile:

error[E0106]: missing lifetime specifier
 --> src/main.rs:7:34
  |
7 | fn fib<T: Zero + One + AddAssign<&T>>(n: usize) -> T {
  |                                  ^ expected lifetime parameter

Rust wants me to add a lifetime parameter to AddAssign<&T> but I don't know how to express the lifetime of f1.

Answer 1

You need to use Higher Rank Trait Bounds. This one means basically "For any lifetime 'a, T satisfies the AddAssign<&'a T> trait":

fn fib<T>(n: usize) -> T
where
    for<'a> T: Zero + One + AddAssign<&'a T>,

I also had to change the way fib is called because the compiler couldn't figure out the return type, which could be literally any type that implements those traits. Declaring x's type gives sufficient context to the compiler so that it knows what you want.

fn main() {
    let x: num::BigUint = fib(10);
    // let x = fib::<BigUint>(10); // Also works
    println!("fib(10) = {}", x);
}

playground