生鏽的類型級乘法

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 HERE節我收到以下錯誤信息：

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 + B」 的結果：現在

<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箱子這是狀態藝術。