Rust类型级乘法

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

我认为你滥用泛型,这是你问题的根源.

Rust中的泛型具有输入和输出:

• 输入被指定为之间的参数 <>
• 输出(也称为关联类型)在类型内指定

直觉是,对于给定的一组输入,为每个输出选择单一类型.

在您的情况下,我们必须为此重新设计特征:

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


// The first attempt does not work, but I'm keeping it here as 
// it is good for learning purpose.
// 
// 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;
// }
//
// Think: 
//   1. Why exactly does it not work? 
//   2. What exactly is going on here?
//   3. How would you multiply numbers in terms of addition? 
//   4. m * n = m + m + m ... (n times)? Or: n + n + .. (m times)?
// 
// Answering these questions will help learning the intricacies of
// Rust's traits/type-system and how they work. 

impl<A: Nat, B: Nat> Mul<B> for Succ<A>
where
    A: Mul<B>,
    B: Add<<A as Mul<B>>::Result>,
{
    type Result = <B 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;
}

请注意,这种Peano算法具有相当令人讨厌的限制,特别是在递归的深度.你的加法是O(N),你的乘法是O(N ^ 2),......

如果您对更有效的表示和计算感兴趣,我建议您检查最先进的类型箱.