2
\$\begingroup\$

I've implemented the following Fibonacci iterator:

lib.rs

// lib.rs
// num-traits = 0.2.11

extern crate num_traits;

use num_traits::PrimInt;

pub struct Fibonacci<T> {
    curr: T,
    next: T,
}

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

impl<T> Iterator for Fibonacci<T> where T: PrimInt {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.curr + self.next;
        let prev = self.curr;
        self.curr = self.next;
        self.next = next;
        Some(prev)
    }
}

main.rs

// main.rs

use my_crate::Fibonacci;

fn main() {
    let fibonacci: Vec<u128> = Fibonacci::new().take(100).collect();
    println!("{:?}", fibonacci);
}

I want to make sure that I'm following proper naming conventions and that the code is well-implemented, both in terms of correctness and performance.

Thanks,

\$\endgroup\$
1
\$\begingroup\$

You're pretty good as-is, but there's a few things that could be changed:

extern crate is no longer needed

In Rust 2018 edition, extern crate is no longer needed unless you're using it with #[macro_use].

Detect overflow

Your program could panic (debug mode) or worse, produce weird values (release mode) when it overflows. Instead, use:

let next = self.curr.checked_add(&self.next)?;

This uses the fancy ? operator to return None when that function returns None, stopping the iterator.

Provide a Default implementation

It's handy to be able to create an automatic default implementation for use in derived structs. See this example:

#[derive(Default)]
struct Foo {
    data: u32,
    fib: Fibonacci<u128>,
}

By implementing Default, you make it easy for your users to use your type later on. Someone can just say Foo::default() without writing any initialization code.

(Optional) Derive more traits

Several traits could be helpful in your application, such as Debug which would allow you to see the inside of the generator, and Clone to create a new generator with the same state. This is especially helpful when putting your struct in another struct which uses those traits, as I normally throw at least a #[derive(Debug)] on all my structs. Normally, this is done with the #[derive()] macro:

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

However, you'd loose out on types that aren't i.e. Copy, such as BigInts that are heap-allocated. In that case, you can do:

use std::fmt;

impl<T: Copy> Copy for Fibonacci<T> {}

impl<T: Clone> Clone for Fibonacci<T> {
    fn clone(&self) -> Self {
        Self {
            curr: self.curr.clone(),
            next: self.next.clone(),
        }
    }
}

impl<T: PartialEq> PartialEq for Fibonacci<T> {
    fn eq(&self, rhs: &Self) -> bool {
        self.curr == rhs.curr && self.next == rhs.next
    }
}

impl<T: fmt::Debug> fmt::Debug for Fibonacci<T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Fibonacci")
         .field("curr", &self.curr)
         .field("next", &self.next)
         .finish()
    }
}

(note that I normally prefer the T: Trait syntax. You can use where instead) Unfortunately, yes, that does create a lot of repeated noise. However, you require that your types are PrimInts anyways, so you will never have a type that isn't Copy, Clone, Debug, or PartialEq. But the end result isn't much prettier:

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

impl<T> Fibonacci<T> where T: Copy + Clone + Debug + PartialEq + PrimInt {
    pub fn new() -> Self {
        Self { curr: T::zero(), next: T::one() }
    }
}

impl<T> Default for Fibonacci<T> where T: Copy + Clone + Debug + PartialEq + PrimInt {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Iterator for Fibonacci<T> where T: Copy + Clone + Debug + PartialEq + PrimInt {}

One way to fix this is to create a new trait that has all five of those bounds. In fact, there's a current issue to do just that. However, we can create our own trait in the meantime to fix that:

pub trait Primitive: Copy + Clone + Debug + PartialEq + PrimInt {}
impl<T: Copy + Clone + Debug + PartialEq + PrimInt> Primitive for T {}

So now we have:

use std::fmt::Debug;

pub trait Primitive: Copy + Clone + Debug + PartialEq + PrimInt {}
impl<T: Copy + Clone + Debug + PartialEq + PrimInt> Primitive for T {}

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

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

impl<T> Default for Fibonacci<T> where T: Primitive {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Iterator for Fibonacci<T> where T: Primitive {}

So, all in all, you don't have to do this if you don't want, as it's quite source-heavy.

(Optional) use mem::replace

This part:

fn next(&mut self) -> Option<Self::Item> {
    let next = self.curr + self.next;
    let prev = self.curr;
    self.curr = self.next;
    self.next = next;
    Some(prev)
}

Can be changed to:

use std::mem;

fn next(&mut self) -> Option<Self::Item> {
    let next = self.curr + self.next;
    let prev = mem::replace(&mut self.curr, self.next);
    self.next = next;
    Some(prev)
}

It's not any faster or shorter, but it's your choice whether it expresses your intent better. I think it does, but it doesn't matter that much.

Final code

use num_traits::PrimInt;
use std::mem;
use std::fmt::Debug;

pub trait Primitive: Copy + Clone + Debug + PartialEq + PrimInt {}
impl<T: Copy + Clone + Debug + PartialEq + PrimInt> Primitive for T {}

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

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

impl<T> Default for Fibonacci<T> where T: Primitive {
    fn default() -> Self {
        Self::new()
    }
}

impl<T> Iterator for Fibonacci<T> where T: Primitive {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.curr.checked_add(&self.next)?;
        let prev = mem::replace(&mut self.curr, self.next);
        self.next = next;
        Some(prev)
    }
}
| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

You are calculating next but it will not be used until two calls later, so when you reach the end of the range of the data type the code will overflow before you get the last values calculated.

The trait you are using is num_traits::identities and not num_traits::PrimInt so I guess it should be where T: num_traits::identities

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.