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));
}