How to write a simple generic function with numeric types?


#1

Greetings!

To slowly increase my understanding of Rust, I attempted to write a very simple version of the Fibonacci function (This is the most naïve, simple implementation; it is possible to transform it in an iterative solution but that distracts from its simplicity and therefore from the question):

fn fib(n: u32) -> u32 {
    match n {
        0 => 1,
        1 => 1,
        _ =>     fib(n - 1) + fib(n - 2),
    }
}

(Try it at the Rust Playground )

Now, I want to change this function to work with any (positive) numeric types, and not only u32s. However, transforming fib in a generic version has me stumped. This is what I came up with so far:

use std::ops::{Add, Sub};

fn fib<T: Add + Sub + Ord>(n: T) -> T {
    match n {
        0 => 1,
        1 => 1,
        _ =>     fib(n - 1) + fib(n - 2),
    }
}

(Try it on the Rust Playground)

The compiler tells me that something is missing. If I’m understanding its helpful error messages properly, the problems are:

  • expected type parameter, found integral variable: I need to specify how to transform a literal integer into a value of type T. Is there a trait that does that?
  • Likewise, the trait ```std::ops::Add is not implemented for <T as std::ops::Sub>::Output```` seems to indicate thatn - 1andn - 2cannot be turned back into a value of typeT`.
  • It also seems the case that because std::ops::Add and std::ops::Sub are not always isomorphic in their types (i.e. SystemTime = SystemTime - Duration, here the RHS and LHS of the subtraction operator are different), that this needs to be enforced somehow.

How can this be done? Am I even on the right track with my approach?


#2

Take a look at the traits in the “num” package.


#3

Note that T: Add + Sub + Ord requires that type T is a type that:

  • a type can be added with T
  • a type can be subtracted with T
  • a type can be compared with T

What it doesn’t specify

  • addition of T and T gives T
  • subtraction of T and T gives T
  • T is an integer

For addition and subtraction, you can do the following

fn fib<T: Add<Output=T> + Sub<Output=T> + Ord>(n: T) -> T {

However, that doesn’t require an integer type (required by 1). You can do so by using Num trait from num crate, and then using T::one() instead of 1.


#4

Here’s a crude example: https://is.gd/hyRRMX

As others mentioned, try the num crate.


#5

Side-stepping the base cases, https://is.gd/K4qIi3 works fine. Perhaps using T::one() etc. will allow the base cases to be treated too.