# 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;

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!