Implement a generic Fibonacci sequence in Rust without using Copy trait

Question

I'm trying to learn Rust and am a beginner. How does one go about implementing a generic version of the Fibonacci sequence without using Copy trait in Rust? My code is given below.

I had to use Copy trait, otherwise the compiler would complain

cannot move out of borrowed content [E0507]

in the method next() (everywhere I have borrowed from self). I understand the error, but I'm not sure how this could be done without copying. Also, other comments and observations are welcome!

lib.rs

pub mod fib_trait;

#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
    }
}

fib_trait.rs

extern crate num;

pub mod fib_trait {

    use fib_trait::num::traits::*;
    use std::ops::Add;

    #[derive(Clone, Copy)]
    pub struct Fibonacci<T> where
    T : Zero + One + Add + Copy {
        curr : T,
        next : T,
    }

    impl<T> Fibonacci<T> where 
    T : Zero + One + Add  + Copy{
        pub fn new() -> Fibonacci<T> {
            Fibonacci {
                curr : T::zero(),
                next : T::one(),
            }
        }
    }

    impl<T> Iterator for Fibonacci<T> where
    T : Zero + One + Add + Copy {
        type Item = T;

        fn next(&mut self) -> Option<T> {
            let c : T = self.next;
            self.next = self.next + self.curr;
            self.curr = c;
            let n : T = self.next;
            Some(n)
        }
    }

    #[test]
    pub fn fib_test() {
        let mut f : Fibonacci<u32> = Fibonacci::new();
        assert_eq!(f.next(), Some(1));

        let mut next_val = 1;
        let mut curr_val = 0; 
        for i in Fibonacci::<u32>::new().take(4) {
            let c = next_val;
            next_val = curr_val + next_val;
            curr_val = c;
            assert_eq!(i, next_val);
        }
    }
}

Answer 1

You can use Clone instead of Copy. This requires adding .clone() calls where the compiler did a copy when the Copy bound was present.

extern crate num;

pub mod fib_trait {
    use num::traits::*;
    use std::ops::Add;

    #[derive(Clone, Copy)]
    pub struct Fibonacci<T>
        where T: Zero + One + Add + Clone
    {
        curr: T,
        next: T,
    }

    impl<T> Fibonacci<T>
        where T: Zero + One + Add + Clone
    {
        pub fn new() -> Fibonacci<T> {
            Fibonacci {
                curr: T::zero(),
                next: T::one(),
            }
        }
    }

    impl<T> Iterator for Fibonacci<T>
        where T: Zero + One + Add + Clone
    {
        type Item = T;

        fn next(&mut self) -> Option<T> {
            let c: T = self.next.clone();
            self.next = self.next.clone() + self.curr.clone();
            self.curr = c;
            let n: T = self.next.clone();
            Some(n)
        }
    }

    #[test]
    pub fn fib_test() {
        let mut f: Fibonacci<u32> = Fibonacci::new();
        assert_eq!(f.next(), Some(1));

        let mut next_val = 1;
        let mut curr_val = 0;
        for i in Fibonacci::<u32>::new().take(4) {
            let c = next_val;
            next_val = curr_val + next_val;
            curr_val = c;
            assert_eq!(i, next_val);
        }
    }
}

We can eliminate the clones on the addition by requiring and using addition on references instead of direct values. for<'a> introduces a higher-rank trait bound – we need this because we want &'a T to implement Add<Output=T>, whatever the lifetime 'a is.

extern crate num;

pub mod fib_trait {
    use num::traits::*;
    use std::ops::Add;

    #[derive(Clone, Copy)]
    pub struct Fibonacci<T>
        where T: Zero + One + Clone,
              for<'a> &'a T: Add<Output=T>
    {
        curr: T,
        next: T,
    }

    impl<T> Fibonacci<T>
        where T: Zero + One + Clone,
              for<'a> &'a T: Add<Output=T>
    {
        pub fn new() -> Fibonacci<T> {
            Fibonacci {
                curr: T::zero(),
                next: T::one(),
            }
        }
    }

    impl<T> Iterator for Fibonacci<T>
        where T: Zero + One + Clone,
              for<'a> &'a T: Add<Output=T>
    {
        type Item = T;

        fn next(&mut self) -> Option<T> {
            let c: T = self.next.clone();
            self.next = &self.next + &self.curr;
            self.curr = c;
            let n: T = self.next.clone();
            Some(n)
        }
    }

    #[test]
    pub fn fib_test() {
        let mut f: Fibonacci<u32> = Fibonacci::new();
        assert_eq!(f.next(), Some(1));

        let mut next_val = 1;
        let mut curr_val = 0;
        for i in Fibonacci::<u32>::new().take(4) {
            let c = next_val;
            next_val = curr_val + next_val;
            curr_val = c;
            assert_eq!(i, next_val);
        }
    }
}

---

Also, note the stylistic changes I made above:

• line break before where
• indent where clause
• no space before :

Answer 2

1. extern crate should almost always be placed at the crate root (lib.rs or main.rs). Experience has shown that the paths that result when a crate is imported in submodules are too confusing for most people.

2. There is nothing of substance in lib.rs. This is common for programmers coming from other languages where it's idiomatic to place one object per file. There's generally no need to have files for ceremonial reasons.

3. A mod declaration should almost never be created inside of a file of the same name (mod foo in a foo.rs). This would place the code in two modules. Since the crate is named fib_traits, the type's full path is fib_traits::fib_trait::fib_trait::Fibonacci. I'd hope most people would agree that's unwieldy.

4. There's no space before a colon (:).

5. where clauses go on the line after the type or function. Multiple constraints should be placed on separate lines, and the opening curly brace is on the following line.

6. I prefer to not place trait bounds unless the block needs it. For example, the Fibonacci struct doesn't need a where clause. You may wish to keep it on constructors though, as that allows for earlier error reporting.

7. It's a good idea to always derive Debug for types.

8. There are extraneous type specifiers on let statements. This is common for programmers coming from languages like (older) C++ or (older) Java where the programmer was required to specify the same type multiple times. Rust's type inference is generally capable.

9. There are extra variables that don't provide semantic benefit.

10. The test code is a direct duplication of the production logic. If one had a logic error, it's highly likely the other one would as well. Using an alternate testing strategy (even just hard coding known-good values) prevents that.

11. The test appears to be testing two separate conditions. Either both conditions are important and distinct, in which case they should be separated and given useful names to distinguish them, or the redundant ones should be deleted.

12. Most projects will want to segregate each modules tests into a submodule. This avoids compiling them at all when not building tests.

13. self.next is consumed twice - once when it's added and once when it is returned. In addition, one copy needs to live in the struct to be available for the next iteration. We can avoid consuming the value when adding it by instead adding two references. Repeating the addition gives us one value to store and one to return. We also are required to be more careful about moving the values between struct fields, as moving out the value would leave our structure in an invalid state.

lib.rs

extern crate num;

use num::traits::*;
use std::ops::Add;
use std::mem;

#[derive(Debug, Copy, Clone)]
pub struct Fibonacci<T> {
    curr: T,
    next: T,
}

impl<T> Fibonacci<T>
    where T: Zero + One
{
    pub fn new() -> Fibonacci<T> {
        Fibonacci {
            curr: T::zero(),
            next: T::one(),
        }
    }
}

impl<T> Iterator for Fibonacci<T>
    where T: Zero + One,
    for <'a, 'b> &'a T: Add<&'b T, Output = T>,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        let next1 = (&self.next) + (&self.curr);
        let next2 = (&self.next) + (&self.curr);

        self.curr = mem::replace(&mut self.next, next1);
        Some(next2)
    }
}

#[test]
fn fib_test() {
    let values: Vec<i32> = Fibonacci::new().take(4).collect();
    assert_eq!(values, [1, 2, 3, 5]);
}