generics - ¿Cómo escribir un rasgo limitado para agregar dos referencias de un tipo genérico?

rust fibonacci

Question

Tengo una estructura de Fibonacci que se puede usar como iterador para cualquier cosa que implemente One , Zero , Add y Clone . Esto funciona muy bien para todos los tipos enteros.

Quiero usar esta estructura para los tipos BigInteger que se implementan con un Vec y son caros para llamar a clone() . Me gustaría usar Add en dos referencias a T que luego devuelve una nueva T (sin clonación).

Por mi vida, no puedo hacer uno que compile ...

Trabajando:

extern crate num;

use std::ops::Add;
use std::mem;
use num::traits::{One, Zero};

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

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

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

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = self.next.clone() + self.curr.clone();
        Some(self.curr.clone())
    }
}

#[test]
fn test_fibonacci() {
    let first_12 = new::<i64>().take(12).collect::<Vec<_>>();
    assert_eq!(vec![1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], first_12);
}

Deseado:

extern crate num;

use std::ops::Add;
use std::mem;
use num::traits::{One, Zero};

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

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

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

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = &self.next + &self.curr;
        Some(self.curr.clone())
    }
}

#[test]
fn test_fibonacci() {
    let first_12 = new::<i64>().take(12).collect::<Vec<_>>();
    assert_eq!(vec![1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144], first_12);
}

Esto da el error

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:27:21
   |
27 |         self.next = &self.next + &self.curr;
   |                     ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 25:5...
  --> src/main.rs:25:5
   |
25 | /     fn next(&mut self) -> Option<T> {
26 | |         mem::swap(&mut self.next, &mut self.curr);
27 | |         self.next = &self.next + &self.curr;
28 | |         Some(self.curr.clone())
29 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:21
   |
27 |         self.next = &self.next + &self.curr;
   |                     ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime ''a as defined on the impl at 19:1...
  --> src/main.rs:19:1
   |
19 | / impl<''a, T: Clone + ''a> Iterator for Fibonacci<T>
20 | | where
21 | |     &''a T: Add<&''a T, Output = T>,
22 | | {
...  |
29 | |     }
30 | | }
   | |_^
note: ...so that types are compatible (expected std::ops::Add, found std::ops::Add<&''a T>)
  --> src/main.rs:27:32
   |
27 |         self.next = &self.next + &self.curr;
   |                                ^

error[E0495]: cannot infer an appropriate lifetime for borrow expression due to conflicting requirements
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 25:5...
  --> src/main.rs:25:5
   |
25 | /     fn next(&mut self) -> Option<T> {
26 | |         mem::swap(&mut self.next, &mut self.curr);
27 | |         self.next = &self.next + &self.curr;
28 | |         Some(self.curr.clone())
29 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^
note: but, the lifetime must be valid for the lifetime ''a as defined on the impl at 19:1...
  --> src/main.rs:19:1
   |
19 | / impl<''a, T: Clone + ''a> Iterator for Fibonacci<T>
20 | | where
21 | |     &''a T: Add<&''a T, Output = T>,
22 | | {
...  |
29 | |     }
30 | | }
   | |_^
note: ...so that reference does not outlive borrowed content
  --> src/main.rs:27:34
   |
27 |         self.next = &self.next + &self.curr;
   |                                  ^^^^^^^^^^

Answer 1

¿Cómo escribir un rasgo limitado para agregar dos referencias de un tipo genérico?

Comencemos con un ejemplo simplificado:

fn add_things<T>(a: &T, b: &T) {
    a + b;
}

Esto tiene el error

error[E0369]: binary operation `+` cannot be applied to type `&T`
 --> src/lib.rs:2:5
  |
2 |     a + b;
  |     ^^^^^
  |
  = note: an implementation of `std::ops::Add` might be missing for `&T`

Como sugiere el compilador, debemos garantizar que Add se implemente para &T Podemos expresar eso directamente agregando una vida útil explícita a nuestros tipos y también usándolo en nuestros límites de rasgos:

use std::ops::Add;

fn add_things<''a, T>(a: &''a T, b: &''a T)
where
    &''a T: Add,
{
    a + b;
}

A continuación, intentemos un enfoque ligeramente diferente: en lugar de recibir una referencia, crearemos una dentro de la función:

fn add_things<T>(a: T, b: T) {
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

Obtenemos el mismo error:

error[E0369]: binary operation `+` cannot be applied to type `&T`
 --> src/lib.rs:5:5
  |
5 |     a_ref + b_ref;
  |     ^^^^^^^^^^^^^
  |
  = note: an implementation of `std::ops::Add` might be missing for `&T`

Sin embargo, intentar agregar la misma solución que antes no funciona. También es un poco incómodo porque la vida útil no está asociada con ninguno de los argumentos pasados:

use std::ops::Add;

fn add_things<''a, T: ''a>(a: T, b: T)
where
    &''a T: Add,
{
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

error[E0597]: `a` does not live long enough
  --> src/lib.rs:7:17
   |
3  | fn add_things<''a, T: ''a>(a: T, b: T)
   |               -- lifetime `''a` defined here
...
7  |     let a_ref = &a;
   |                 ^^
   |                 |
   |                 borrowed value does not live long enough
   |                 assignment requires that `a` is borrowed for `''a`
...
11 | }
   | - `a` dropped here while still borrowed

Colocar ''a vida útil en el impl significa que la persona que llama del método puede determinar cuál debería ser la vida útil. Como la referencia se toma dentro del método, la persona que llama nunca puede ver cuál sería esa vida útil.

En su lugar, desea colocar una restricción de que una referencia de una vida arbitraria implemente un rasgo. Esto se llama un Límite de Rasgo de Clasificación Superior (HRTB):

use std::ops::Add;

fn add_things<T>(a: T, b: T)
where
    for<''a> &''a T: Add,
{
    let a_ref = &a;
    let b_ref = &b;

    a_ref + b_ref;
}

Aplicado de nuevo a su código original, estaba muy cerca:

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

    fn next(&mut self) -> Option<T> {
        mem::swap(&mut self.next, &mut self.curr);
        self.next = &self.next + &self.curr;
        Some(self.curr.clone())
    }
}

Ver también:

• ¿Cómo escribo las vidas para referencias en una restricción de tipo cuando una de ellas es una referencia local?
• ¿Cómo difiere la sintaxis para <> de un límite de vida normal?
• ¿Cómo requiero que un tipo genérico implemente una operación como Agregar, Sub, Mul o Div en una función genérica?