Generic Parameters v.s. Associated Types

在学习和使用Rust的过程中会碰到两个概念 泛型参数（Generic Parameters）和 关联类型（Associated Types），有不少人（包括我自己）有时会混淆这两种类型。比如 有人会问，为什么描述闭包的Fn/FnMut/FnOnce trait，其返回值用关联类型来描述，而不是泛型。与其它语言有所不同，比如scala的Function1[-T1, +R]。

关于这两种类型的选择，这里写下自己的一些理解。

稍微限定一下前提，这里的泛型参数指的是trait上的泛型参数：

trait Foo<T> {
       // ^
       // +---- 这个泛型参数
    type A; // <---- 这个关联类型
}

与关联类型相对应的概念在Haskell中称为type families（type class中的）。规则上大概是这样，泛型和Self 与 关联类型 是 n对1的关系：

换句话说就是当泛型和Self确定下来的时候，其关联类型也要确定下来，通过这种方式来消除一些trait的歧义。比如已经给Range<i32>实现了Iterator，其Item为i32，我们就不能再实现另一个Iterator<Item=u32>了。总之，关联类型在trait里充当一个类型的“占位符”，表示“存在一个类型”，它在定义(impl)时，便要确定具体的类型了（而泛型是在调用时才决定具体类型）。

就这样的定义，似乎有点抽象。但使用上，其实有个比较简单的法则，去帮助你思考你的trait应该使用泛型还是关联类型：

1. 具体类型由caller来决定的，使用泛型参数。

   一般使用在method的参数处（也不全是，比如Into trait）

   xxxxxxxxxx
     pub trait Consumer<T> {
         fn consume(&self, v: T);
     }
     
     x.consume('a');
     // 完整调用
     <X as Consumer<char>>::consume(x, 'a')
     //              ^
     //              +--- 在调用时决定具体类型(可以推导出来，可省略)
   

   而函数的返回值处一般拿不到泛化的类型（不通过参数），如果将trait泛型放置于方法返回值处，大多数情况就要单独实现不同的trait了（就像Into 一样，但是Into可由From trait自动实现）。

2. 具体类型由callee来决定的，使用关联类型。

   一般用在方法返回值处中（Into trait也是个特例）：

   xxxxxxxxxx
   struct Once<T>(Option<T>);
   ​
   impl<T> Iterator for Once<T> {
       type Item = T; // 一个Once<T> 对应一个 T
       fn next(&mut self) -> Option<Self::Item> { 
           self.0.take() // 由实现(callee)决定Item的类型
       }
   }
   

   或者回调的参数中：

   xxxxxxxxxx
   trait Schedule {
       type Next;
       fn schedule(&mut self, f: &mut dyn FnMut(Self::Next));
   }
   ​
   struct Fact(u32, u64);
   ​
   impl Schedule for Fact {
       type Next = u64; // 一个Fact关联一个u64
       fn schedule(&mut self, f: &dyn Fn(Self::Next)) {
           if self.0 == 0 {
               f(self.1); // 由实现决定Next的类型
           } else {
               self.1 *= self.0;
               self.0 -= 1;
               self.schedule(f);
           }
       }
   }
   

   因为callee中的类型，是在实现时就确定下来的。对于确定的泛型和Self，它就是唯一的。所以它并没有多态性，如果放在method参数上，要放不同的类型的参数，就要写多个类似的结构，所以一般不会用在method的参数上。这样也解释了为什么FnOnce trait为什么要将返回类型设计为关联类型，当一个闭包写下来的时候，其返回类型是确定的，而且还有一个重要的原因是，rust没有scala那样的子类型关系，所以无法进行类似的推导。

不过在关联类型处有时候也有“多态”的需求：

1. 回调不同类型的参数：

   xxxxxxxxxx
   trait Foo {
       type F;
       fn do_something(&self, f: &dyn Fn(Self::F));
   }
   ​
   impl Foo for X {
       type F = ???;
       fn do_something(&self, f: &dyn Fn(Self::F)) {
           f(1);
           f('a');
           f(vec![1,2,3]);
       }
   }
   

2. 返回不同类型的结果：

   xxxxxxxxxx
   impl Iterator for X {
       type Item = ???;
       fn next(&mut self) -> Option<Self::Item> {
           match xxx {
               a => Some(1),
               b => Some('a'),
               _ => Some(vec![1,2,3])
           }
       }
   }
   

   嘛……这种”多态“也是伪多态，其实是确定的几种类型，解决方法也很简单，用enum包一下，或是用trait object，这里就不用展开了。而对于是引生命周期不一致的，还可以用高阶生命周期（higher-ranked trait bound）：

   xxxxxxxxxx
   trait Foo {
       type F;
       fn do_something(&self, f: &dyn for<'a> Fn(&'a Self::F));
       //                                  ^--- 表示可以应用借用任意的“长度”的引用（其实可以elid掉）
   }
   ​
   impl Foo for X {
       type F = A;
       fn do_something(&self, f: &dyn for<'a> Fn(&'a Self::F)) { 
           let a1 = /*xxx*/;
           f(&a1); // 'a确定为一个局部的生命周期
           f(&/*xxx*/); // 'a确定为'static或者temperory的生命周期
           // 几个引用类型不一样
       }
   }
   

    

最后再解决一个trait泛型中的一个常见问题，“未限形参”（unconstrained type parameter）：

xxxxxxxxxx
error[E0207]: the type parameter `S` is not constrained by the impl trait, self type, or predicates
  --> src\ops.rs:12:6
   |
12 | impl<S, Lhs, Rhs> BitOr<Rhs> for ParserWrapper<Lhs>
   |      ^ unconstrained type parameter
​

如果泛型参数没有出现在：

1. Self类型中（比如上面的ParserWrapper<Lhs>）
2. trait的实现中（比如上面的BitOr<Rhs>和method签名中，不包括关联类型）
3. trait bound的关联类型处（比如impl<A, F: Fn() -> A> 这样是可以的，因为A在F的关联类型中，A被F约束了）

就会出现这种编译错误。

我们来看一下具体的场景，要为Parser trait重载BitOr运算符：

xxxxxxxxxx
pub trait Parser<S> {
    type Target;
    fn parse(&self, stream: &mut S) -> Option<Self::Target>;
}
​
struct ParserWrapper<P> {
    inner: P,
}
​
impl<S, Lhs, Rhs> BitOr<Rhs> for ParserWrapper<Lhs>
where
    Lhs: Parser<S>,
    Rhs: Parser<S>,
{
    type Output = ParserWrapper<Or<Lhs, Rhs>>;
​
    fn bitor(self, rhs: Rhs) -> Self::Output {
        ParserWrapper::new(Or::new(self.inner, rhs))
    }
}

这段代码就会出现刚刚的编译错误，因为这里泛型参数S没被约束（Lhs: Parser<S>，这里并没有限制，S还是任意的）。如果这段代码成立就会造成，对于一个ParserWrapper<Lhs>和一个BitOr<Rhs>多种实现，无法进行区分。

修复这段代码，其实也很简单，可以在ParserWrapper中多加一个泛型参数，make rustc happy：

xxxxxxxxxx
struct ParserWrapper<S, P> {
    inner: P,
    _marker: PhantomData<fn(&mut S)>, 
    // ParserWrapper也是个Parser，S要和parse中的S保持一致
}
​
impl<S, Lhs, Rhs> BitOr<Rhs> for ParserWrapper<S, Lhs> {/*...*/}

这样S就被约束到Self中了。其实在类型上Index一个类型参数还有其它好处，它给编译器提供了更多的类型信息，有时候可以帮助类型推导，也可以利用这个类型参数表示“同型”但不同“性”的数据，这里就不展开说了。

总结

这里提到的法则，也不是通用的，也有不少反例，比如Into/From trait等等，所以仅供参考。。。只要被抽象的东西满足了(Generic, Self) n..1 Associated的关系时，就可以了。

另外Self type其实也可以当作一个泛型参数：

Self may be used in a type annotation to refer to an instance of the type implementing this trait passed as a parameter.

这也解释了，为什么Self和泛型参数用法这么相近了。