How to avoid excessive cloning in Rust?

Question

I'm trying to learn Rust, and like many before me set off to write a Fibonacci sequence iterator for practice. My first pass used u32s and worked fine, so I decided to try to write a generic version. This is my result:

use num::Integer;
use std::ops::Add;

pub struct Fibonacci<T: Integer + Add + Clone> {
    nth: T,
    n_plus_one_th: T,
}

impl<T: Integer + Add + Clone> Iterator for Fibonacci<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        let temp = self.nth.clone();
        self.nth = self.n_plus_one_th.clone();
        self.n_plus_one_th = temp.clone() + self.n_plus_one_th.clone();
        Some(temp)
    }
}

impl<T: Integer + Add + Clone> Fibonacci<T> {
    pub fn new() -> Fibonacci<T> {
        Fibonacci {
            nth: T::one(),
            n_plus_one_th: T::one(),
        }
    }
}

I tested this with a u32 and a num::BigUint, and it works fine. I'm concerned about all the cloning in the next method though. In particular, I don't understand why I need to clone during the addition step.

I suspect there is a better way to write this using some of Rust's more advanced reference concepts, but so far I haven't figured it out.

Answer 1

The solution is to use a where clause like so:

extern crate num;

use num::One;
use std::ops::Add;

pub struct Fibonacci<T> {
    nth: T,
    n_plus_one_th: T,
}

impl<T> Fibonacci<T>
    where T: One
{
    pub fn new() -> Fibonacci<T> {
        Fibonacci {
            nth: T::one(),
            n_plus_one_th: T::one(),
        }
    }
}

impl<T> Iterator for Fibonacci<T>
    where for<'a> &'a T: Add<&'a T, Output = T>
{
    type Item = T;
    fn next(&mut self) -> Option<T> {
        use std::mem::swap;
        let mut temp = &self.nth + &self.n_plus_one_th;
        swap(&mut self.nth, &mut temp);
        swap(&mut self.n_plus_one_th, &mut self.nth);
        Some(temp)
    }
}

Specifically, the for<'a> &'a T: Add<&'a T, Output=T> clause reads as "for any lifetime 'a, &'a T must implement Add with a RHS of &'a T and Output=T. That is, you can add two &Ts to get a new T.

With that, the only remaining issue is shuffling the values around, which can be done using swap.

I also took the liberty of simplifying the constraints elsewhere (you only needed One, not Integer).