I don't understand explicit lifetime parameters


#1

I’m trying to do some basic numerical calculations, but I want to be able to do them irrespective of what numeric type is in use. Specifically, I want these functions to work with either usize or BigUint (from the num crate), and I thought the easiest way to do that would be to create functions with type parameters. Here are the functions as I would like to have them work:

use std::ops::{Add, Mul, Div, Rem};
use std::default::Default;

/// Performs a Horner encoding on the given elements.
pub fn horner<T>(elems: &Vec<T>, alg_sizes: &Vec<T>) -> T
        where T: Default + Add<T,Output=T> + Mul<T,Output=T> {
    let k = elems.len();
    let mut ans: T = Default::default();
    for i in (0..k).rev() {
        ans = alg_sizes[i]*ans+elems[i];
    }
    ans
}

/// Inverts a Horner encoding on the given elements.
pub fn horner_inv<T>(i: T, alg_sizes: &Vec<T>) -> Vec<T>
        where T: Default + Clone + Div<T,Output=T> + Rem<T,Output=T> {
    let mut ans = vec![Default::default();alg_sizes.len()];
    let mut rem = i.clone();
    for j in 0..alg_sizes.len() {
        ans[j] = rem % alg_sizes[j];
        rem = rem / alg_sizes[j];
    }
    ans
}

/// Performs a Horner encoding on the given elements.
pub fn horner_power<T>(elems: &Vec<T>, alg_size: T) -> T
        where T: Default + Add<T,Output=T> + Mul<T,Output=T> {
    let k = elems.len();
    let mut ans: T = Default::default();
    for i in (0..k).rev() {
        ans = alg_size*ans + elems[i];
    }
    ans
}

/// Inverts a Horner encoding on the given element.
pub fn horner_power_inv<T>(i: T, alg_size: T, power: usize) -> Vec<T>
        where T: Default + Clone + Div<T,Output=T> + Rem<T,Output=T> {
    let mut ans = vec![Default::default();power];
    let mut rem = i.clone();
    for j in 0..power {
        ans[j] = rem % alg_size;
        rem = rem / alg_size;
    }
    ans
}

Unfortunately, when I try to compile literally this, I get a lot of movement errors. (Note: BigUint is not Copy, so I can’t rely on Copy semantics here - these functions work fine if I require T to be Copy in each function declaration.) Naturally then, I try to use references instead of literal values, but that requires me to write function signatures like:

pub fn horner<'a,'b,T>(elems: &'b Vec<T>, alg_sizes: &'a Vec<T>) -> T
        where T: Default + Add<&'b T,Output=T>,
            &'a T: Mul<T,Output=T>

and I still get various move errors and complaints from the compiler about values not living long enough. I think that the problem lies with being unable to say something like where &'c T: Mul<&'d T,Output=T> where 'c and 'd are allowed to refer to lifetimes within the scope of the function’s execution itself.

Any suggestions how I could solve this difficulty?


#2

Apparently, the traits for Add and similar are destructive: x = a + b takes ownership and destroys the contents of a and b, leaving only x. Of course, if the types are Copy, it is not relevant. If not, and you need to keep the original value, you probably need to use Clone.

As a side note, your code uses Default, but I suspect it should use Zero instead, and One wherever relevant.


#3

Take a look at the trait bounds here, that might help.

In any case, just requiring Copy is probably a lot easier for numeric types than fiddling with reference types.


#4

Thank you, using for in the trait bounds worked perfectly. Requiring Copy would indeed have been easier, but as I said I wanted this to work with BigUint as well, which isn’t Copy, and I was trying to avoid cloning BigUints everywhere.

As for using Zero instead of Default, I didn’t want to have to load the crate num when necessary (I intend on doing so only in some compilations of the program), and std::num::Zero is listed as unstable, so I figured Default was probably the better choice for the moment.


#5

This is an incomplete answer. You can impl Add<&T> for &T just fine.


#6

If I change the code above to just say something like where T: Add<&T,Output=T>, &T: Mul<T,Output=T> then it tells me to use explicit lifetimes. The same thing happens if I just require &T: Add<&T,Output=T> + Mul<&T,Output=T>.


#7

Yes, but unless I am mistaken, it will still be self, not &self, and more importantly for the discussion at hand, it is not implemented for BigUint.