Ускорение типа ржавчины

Question

Я пытаюсь реализовать умножение на уровне типа в Rust.

Дополнение уже работает, но у меня возникли проблемы с переменной типа «временный».

Код:

use std::marker::PhantomData; 

//Trait for the type level naturals 
trait Nat {} 
impl Nat for Zero {} 
impl<T: Nat> Nat for Succ<T> {} 

//Zero and successor types 
struct Zero; 
struct Succ<T: Nat>(PhantomData<T>); 

//Type level addition 
trait Add<B,C> 
    where Self: Nat, 
     B: Nat, 
     C: Nat 
    {} 

impl<B: Nat> Add<B,B> for Zero {} 
impl<A: Nat,B: Nat,C: Nat> Add<B,C> for Succ<A> 
    where A: Add<Succ<B>,C> 
    {} 

fn add<A: Nat, B: Nat, C: Nat>(
    a: PhantomData<A>, 
    b: PhantomData<B>) 
    -> PhantomData<C> 
    where A: Add<B,C> { PhantomData } 

//Type level multiplication 
trait Mult<B,C> 
    where Self: Nat, 
     B: Nat, 
     C: Nat, 
    {} 

impl<B: Nat> Mult<B,Zero> for Zero {} 

//ERROR HERE: "unconstrained type parameter 'C'" 
//impl<A: Nat, B: Nat,C: Nat, D: Nat> Mult<B,D> for Succ<A> 
// where A: Mult<B,C>, 
//  B: Add<C,D> 
//  {} 


fn main() { 
    let x: PhantomData<Succ<Succ<Zero>>> = PhantomData; 
    let y: PhantomData<Succ<Zero>> = PhantomData; 

    //uncomment ': i32' in the next line to see infered type 
    let z /*: i32*/ = add(x,y); 
} 

Опубликованный код компилируется просто отлично и аддитивная работа. Если я раскомментировать здесь ошибку раздел я получаю следующее сообщение об ошибке:

error[E0207]: the type parameter `C` is not constrained by the impl trait, self type, or predicates 
    --> src/main.rs:40:21 
    | 
40 | impl<A: Nat, B: Nat,C: Nat, D: Nat> Mult<B,D> for Succ<A> 
    |     ^unconstrained type parameter 

error: aborting due to previous error 

error: Could not compile `4_18_generics`. 

To learn more, run the command again with --verbose. 

• Есть ли способ использовать такие «временные промежуточные /» параметры типа?

• Возможно ли умножение любым другим способом (в настоящее время я не думаю)?

• Как правило, это невозможно?

• Возможно ли это в будущей версии языка?

Answer 1

Я думаю, что вы неправильно используете дженерики, и это корень вашей проблемы.

Непатентованные Руст имеют входы и выходы:

• Входы указаны в качестве параметров между <>
• выходов (называемые также связанные с ними типы) указаны внутри типа

Интуиция заключается в том, что для заданного набора входов для каждого выхода выбирается один тип.

В вашем случае, мы должны переработать черты для этого:

trait Add<Rhs: Nat>: Nat { 
    type Result: Nat; 
} 

Определение признака говорит:

• Add требует Self быть Nat
• Add реализуется для правый аргумент, который должен быть Nat
• Данная реализация Add имеет тип Result, который должен быть Nat

Теперь мы можем реализовать:

impl<T: Nat> Add<T> for Zero { 
    type Result = T; 
} 

impl<A: Nat, B: Nat> Add<B> for Succ<A> 
    where A: Add<Succ<B>> 
{ 
    type Result = < A as Add<Succ<B>> >::Result; 
} 

Обратите внимание, что функции являются абсолютно ненужными, результат «А + В» :

<A as Add<B>>::Result 

Теперь, на умножение:

trait Mul<Rhs: Nat>: Nat { 
    type Result: Nat; 
} 

impl<T: Nat> Mul<T> for Zero { 
    type Result = Zero; 
} 

impl<A: Nat, B: Nat> Mul<B> for Succ<A> 
    where A: Mul<B> + Add< <A as Mul<B>>::Result > 
{ 
    type Result = <A as Add< <A as Mul<B>>::Result >>::Result; 
} 

И это сейчас составляет:

fn main() { 
    type One = Succ<Zero>; 
    type Two = <One as Add<One>>::Result; 
    type Four = <Two as Mul<Two>>::Result; 
} 

Обратите внимание, что такая арифметика Пеано имеет довольно досадные ограничения, хотя, в частности, в глубине рекурсии. Ваше дополнение O (N), ваше умножение - O (N^2), ...

Если вас интересуют более эффективные представления и вычисления, я советую вам проверить ящик typenum, который является состоянием Изобразительное искусство.