How to write a simple generic function with numeric types?

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 that n - 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 Likes

Take a look at the traits in the "num" package.

2 Likes

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.

3 Likes

Here's a crude example: Rust Playground

As others mentioned, try the num crate.

2 Likes

Side-stepping the base cases, Rust Playground works fine. Perhaps using T::one() etc. will allow the base cases to be treated too.

2 Likes

I must admit, I've been writing some code that demands Generic numeric types and I'm pretty disappointed that the Rust developers have not come to a consensus on a useful trait hierarchy for numerics. Yeah, there's the num crate, but this is pretty fundamental to the language and it deserves a spot in the standard library!

Looking back on Reddit posts, stuff in this forum, old Rust Docs, and even the latest "Programming Rust" book it looks like the community can't settle on anything and so they've just punted to the third-party num crate.

Even worse, it seems there were prior answers to some questions like One, Zero, FromPrimitive etc, that have been deprecated and removed! Ugh, why make it harder?

Look at what the poor guy had to do above just to write a generic fibonacci sequence generator! Not elegant!

Rather than just end with a rant, I wanted to ask, is there any work going on to standardize numeric traits? Or, are we just going to rely on the third party num crate and treat it as the defacto standard forever? If we're not going to use it forever, what's the time-horizon?

Seems weird that we have a num crate that is the-best-there-is-to-offer, and it's not in the standard library. Why is that?

3 Likes

Because you assume the standard library is for good and useful things that are easy to use. In Rust, that's what crates.io is for.

In Rust the standard library is for:

  1. interface to the compiler for things that can't be done via crates.io crate,
  2. basic minimum required for interoperability between crates,
  3. some mistakes, that Rust wasn't be able to fix or remove before they got frozen.

Rust gives guarantee that stuff in std is final, and won't have any breaking changes. This is a big cost, big risk and shouldn't be taken lightly. I guess num could fall under case #2, but if you were able to use num, then it seems to be good enough to be out of std.

6 Likes