Mnożenie poziomu rdzy

Question

Próbuję wprowadzić mnożenie na poziomie typu w Rust.

Dodawanie już działa, ale mam problemy z "tymczasową" zmienną typu.

Kod:

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); 
} 

Oddelegowany kompiluje kod działa dobrze i dodawania. Gdybym odkomentuj ERROR TUTAJ sekcję otrzymuję następujący komunikat o błędzie:

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. 

• Czy istnieje sposób, aby wykorzystać takie „tymczasowe pośredniej /” Parametry typu?

• Czy mnożenie jest możliwe w jakikolwiek inny sposób (obecnie nie myślę o)?

• Czy generalnie nie jest to możliwe?

• Czy będzie to możliwe w przyszłej wersji językowej?

Answer 1

Myślę, że źle używasz generycznych, i to jest źródłem twojego problemu.

rodzajowych Rust mają wejść i wyjścia:

• Wejścia są określone jako parametry pomiędzy <>
• wyjść (zwane również związane ów) są określone wewnątrz typu

Intuicja jest taka, że ​​dla danego zestawu wejść wybierany jest jeden typ dla każdego wyjścia.

W twoim przypadku, musimy przerobić cechy dla tego:

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

Definicja cechy mówi:

• Add wymaga Self być Nat
• Add jest realizowany za prawy argument, który musi być Nat
• Dany realizacja Add ma Result typ, który musi być Nat

Teraz możemy wdrożyć go:

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; 
} 

Należy zauważyć, że funkcje są całkowicie zbędne, wynik "A + B" :

<A as Add<B>>::Result 

teraz do mnożenia:

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; 
} 

I to teraz kompiluje:

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

Należy pamiętać, że takie arytmetyka Peano ma dość irytujących ograniczeń choć, zwłaszcza w głębi rekursji. Twój dodatek to O (N), twoje mnożenie to O (N^2), ...

Jeśli jesteś zainteresowany bardziej wydajnymi reprezentacjami i obliczeniami, radzę sprawdzić skrzynkę typenum, która jest stanem sztuka.