Lifetimes in a generic numeric function

Hello,

As an exercise in learning Rust, I'm trying to write a generic Fibonacci function. (I know that this is challenging for beginners, but getting it to work would help me in preparing examples for another thread that is ongoing.)

The following is a complete Rust program (it uses the num-bigint crate):

use num_bigint::BigInt;

fn fib(n: usize) -> BigInt {
    let mut f0 = BigInt::from(0);
    let mut f1 = BigInt::from(1);
    for _ in 0..n {
        let f2 = f0 + &f1;
        f0 = f1;
        f1 = f2;
    }
    f0
}

fn main() {
    println!("{}", fib(10));
}

One can replace BigInt by, say, i64, and it continues to work.

Here, I already have one question:
The num-bigint crate shows a similar program as its first example. But there, f0 and f1 are initialized using stuff from num_traits like Zero::zero(). This introduces another dependency - does it have an advantage over simply using BigInt::from(0)? (Assuming that a reasonable numeric type should implement initialization from i32.)

But now for the actual question. I am unable to turn the above into a generic function. My best effort can be seen below, but it does not compile. Obviously I do not get the “lifetimes” right. Thanks in advance for any hints!

use num_bigint::BigInt;
use core::ops::Add;

fn fib<'a, T>(n: usize) -> T
where
    T: From<i32> + Add<&'a T, Output = T> + 'a
{
    let mut f0 = T::from(0);
    let mut f1 = T::from(1);
    for _ in 0..n {
        let f2 = f0 + &f1;
        f0 = f1;
        f1 = f2;
    }
    f0
}

fn main() {
    println!("{}", fib::<BigInt>(10));
}
fn fib<T>(n: usize) -> T
where
    T: From<i32> + for<'a> Add<&'a T, Output = T>

You need HRTB.

playground

2 Likes

Generic type and lifetime (and const) arguments are chosen by the caller. Here, you want the lifetime to be chosen by your own function body instead. You can't generate a reference that is valid at least as long as your function body from within your function body (not to a local variable, at least), so no matter what lifetime the generic is substituted with, your local's address won't satisfy it.

You need a HRTB instead: for<'a> Add<&'a T, Output = T>.

This is false. BigInt already depends on num_traits. There's no additional dependency introduced by using Zero::zero().

Anything that is smaller than i32 doesn't. Nor does u32. (Both for obvious reasons.) So you couldn't call the thing with e.g. u32 or i16 as the return type.

3 Likes

@vague, @H2CO3, thank you very much for your explanations.

I had to add it as a dependency to Cargo.toml, but now I realize that this does not mean that it was not already an indirect dependency.

Of course!