Rust中的泛型

Rust中的泛型

根据Rust 0.6 tutorial整理。

这部分内容鄙人很喜欢，Rust的泛型和Haskell非常类似，所以我将参照着Haskell来叙述。（推荐一下Haskell，看了Haskell之后很多“新鲜”概念就不那么神秘了）

1 泛型函数

Rust是静态类型语言，因此定义函数时要提供参数和返回值的类型，提供了类型之后，函数就只能作用于给定的类型了。如果我们不提供具体类型，而是提供类型参数（类似Haskell中的类型变量），那么函数就能作用于很多类型了，所以叫泛型：

fn map(vector: &[T], function: fn(v: &T) -> U) -> ~[U] {
    let mut accumulator = ~[];
    for vec::each(vector) |element| {
        accumulator.push(function(element));
    }
    return accumulator;
}

如上例所示，map就是一个泛型函数，类型参数为<T, U>。它接受一个向量参数vector和一个函数参数function，其中vector的元素类型为T；function参数类型&T（为了保证通用性，因为有些类型的拷贝代价高昂，甚至不允许拷贝），返回类型为U；map返回类型为~[U]。map函数对vector中的每个元素调用函数function，然后将得到的结果装入新的向量，最后返回该向量。

我们看一下Haskell中类似的实现，就会发现两者很类似，只不过Haskell中类型变量惯例用小写。

my_map :: [t] -> (t -> u) -> [u]
my_map [] _ = []
my_map (x:xs) f = (f x):(my_map xs f)

2 泛型类型

我们之前定义的type、struct和enum中，每个数据域的类型都是固定的。Rust允许数据域的类型不固定，而由类型参数给出，如下所示：

type Set = HashMap;

struct Stack {
    elements: ~[mut T]
}

enum Option {
    Some(T),
    None
}

和泛型函数类似，类型参数写在<>中。这些泛型就可以实例化为Set<int>，Stack<int>和Option<int>这样的具体类型。

而在Haskell中，上述类型定义对应为：

type Set t = HashMap t () 

data Stack t = Stack [t]

data Option t = Some t
              | None

熟悉Haskell的估计已经看出来，Rust中的Option就是Haskell中的Maybe。而Rust的stuct和enum在Haskell中都是data。

Option在Rust中使用频率很高。因为Rust中没有null指针（除了unsafe code），所以需要用Option来应对不存在的情况。例如：

fn radius(shape: Shape) -> Option {
   match shape {
       Circle(_, radius) => Some(radius),
       Rectangle(*)      => None
   }      
}

Rust编译器可以高效地编译泛型函数，通过对泛型函数进行monomorphizing。Monomorphization是一种简单的方法：在每个调用点为泛型函数生成单独的拷贝，该拷贝根据参数类型对函数进行实例化，所以可以针对参数类型进行优化。因此，Rust的泛型有着与C++模板类似的性能。

3 Traits

泛型函数中能对类型参数进行的操作是很有限的，毕竟不知道具体的类型，所以不能安全地对它们进行修改或者查询它们的值。这就是为什么需要trait的原因。Traits是Rust中编写多态代码的强大工具。Java程序员会发现traits很像Java的interface。Haskeller也会发现它们很像type classes（确实如此）。Rust的traits是一种bounded polymorphism：trait用来限定类型参数所能代表的类型种类。

我们看一下trait的具体应用。在Rust中，不是所有类型都有copy操作。用户自定义析构函数是不能copy的一个原因：拷贝一个带有析构函数的类型可能会使析构函数被多次调用。因此，有用户自定义析构函数的类型不能拷贝（无论是隐式拷贝还是显式拷贝），而其它类型也不能包含有着析构函数的类型。

这就复杂化了对泛型函数的处理。如果类型参数为T，我们可以拷贝它的值吗？在Rust中，你不能，如果试图运行下面的代码，编译器会发出抱怨：

// This does not compile
fn head_bad(v: &[T]) -> T {
    v[0] // error: copying a non-copyable value
}

然而，如果我们告诉编译器head函数只作用于能够copy的类型：也就是那些实现了Copy trait的类型：

// This does
fn head(v: &[T]) -> T {
    v[0]
}

这就意味着head函数只能作用于实现了Copy trait的类型。当实例化泛型函数时，你只能用实现了正确trait的类型来进行实例化，所以不能将head函数应用于有析构函数的类型（Copy是一个特殊的trait，编译器自身内置，使得编译器能够强制实行该限制）。

虽然大部分traits都可以由用户自定义和实现，但是有三个trait是由编译器自动推导和实现的，用户不能覆盖：

• Copy——可以被拷贝的类型：通过隐式拷贝，或者copy运算符显式拷贝。除了有析构函数的类型和包含了有析构函数类型的类型外，所有的类型都是可拷贝的。
• Owned——Owned types。除了包含有managed boxes, managed closures，和borrowed pointers的类型外，其他类型都属于owned。Owned类型可能可以拷贝，也可能不能拷贝。
• Const——常量（不可变的）类型。指没有包含可变域的类型。

另外，Drop trait用来定义析构函数。该trait定义了finalize函数，该函数在实现了Drop的类型的值被销毁时自动调用（当值超出作用域，或者垃圾回收时）。

struct TimeBomb {
    explosivity: uint,
}

impl TimeBomb : Drop {
    fn finalize(&self) {
        for iter::repeat(self.explosivity) {
            io::println("blam!");
        }
    }
}

直接调用finalize是非法的。只有由编译器插入的代码才可以调用它。

4 声明和实现traits

trait包含了一组方法，这些方法没有函数体，或者为空。例如，我们声明一个名为Printable的trait，有一个print方法：

trait Printable {
    fn print(&self);
}

这在Haskell中对应于type class：

class Printable a where
    my_print :: a -> IO ()

Traits由具体类型来实现，实现由impl关键字引出，和为类型定义方法类似，不过多了trait相关说明：

impl int: Printable {
    fn print(&self) { io::println(fmt!("%d", *self)) }
}

impl &str: Printable {
    fn print(&self) { io::println(*self) }
}

对应于Haskell中对typeclass的实例化：

{-# LANGUAGE TypeSynonymInstances, FlexibleInstances #-}  
 
instance Printable Int where
    my_print i = print i
  

instance Printable String where
    my_print str = print str

Trait的实现中定义的方法调用起来和其他的方法一样，使用点记法，如1.print()。Traits也可以包含类型参数。带有类型参数的trait如下所示：

trait Seq {
    fn len(&self) -> uint;
    fn iter(&self, b: fn(v: &T));
}

impl ~[T]: Seq {
    fn len(&self) -> uint { vec::len(*self) }
    fn iter(&self, b: fn(v: &T)) {
        for vec::each(*self) |elt| { b(elt); }
    }
}

上述实现中必须明确声明类型参数（impl<T>）。声明后才能使用T来指明trait类型（Seq<T>）。Rust要求这么做是因为：impl也可以用来定义Seq<int>这样的实现。trait的类型（冒号后的部分，Seq<T>）参考了一个类型（T），而不是定义了一个类型。

Trait绑定的类型参数对于trait的每一个方法都是可见的。所以，对于trait中的方法，不管是trait中声明，还是impl中实现 ，都不需要再明确指明类型参数（比如：fn len<T>(&self) -> uint），否则将引起编译错误。

在trait定义中，self是一个特殊的类型，你可以认为它是一个类型参数。一个针对类型T的trait实现会把self替换为T。简单地说，在trait中，self是一个类型，而在impl中，self是一个值。下面的trait描述了支持相等操作的类型：

// In a trait, `self` refers both to the self argument
// and to the type implementing the trait
trait Eq {
  fn equals(&self, other: &self) -> bool;
}

// In an impl, `self` refers just to the value of the receiver
impl int: Eq {
  fn equals(&self, other: &int) -> bool { *other == *self }
}

注意在上面trait定义中，equals第二个参数的类型为self。相应的，在impl中，equals第二个参数类型为int，只使用self作为接收者的名字。

Traits也可以定义静态方法，然后通过trait名字前缀来调用。编译器通过类型推导来判断调用哪个实现。

struct Circle { radius: float }
struct Square { length: float }

impl Circle: Shape {
    static fn new(area: float) -> Circle { Circle { radius: sqrt(area / pi) } }
}
impl Square: Shape {
     static fn new(area: float) -> Square { Square { length: sqrt(area) } }
}

let area = 42.5;
let c: Circle = Shape::new(area);
let s: Square = Shape::new(area);

5 类型参数限定和静态方法分配

前面说了，在泛型函数中，我们能对类型参数所做的事情很有限。因为不知道类型参数的具体类型，也就不知道它所能支持的操作。有了traits之后，我们就能使用traits来限定类型参数，指明其具有的操作或者抽象属性。

fn print_all(printable_things: ~[T]) {
    for printable_things.each |thing| {
        thing.print();
    }
}

上例中，我们声明T为实现了Printable trait的类型，因此类型T的值就可以调用Printable中声明的方法。同时，如果对以未实现Printable的类型的值为元素的向量调用print_all时，就会引发编译错误。
类型参数也可以由多个traits限定，用空格分隔trait即可，比如下面版本的print_all：

fn print_all(printable_things: ~[T]) {
    let mut i = 0;
    while i < printable_things.len() {
        let copy_of_thing = printable_things[i];
        copy_of_thing.print();
        i += 1;
    }
}

调用含有限定类型的方法时使用的是静态分配。和普通的函数调用相比没有额外开销，因此也是最受欢迎的traits多态方式。（注：因为类型已经被trait限定，而trait中声明的方法也已经被实现，所以调用时不需要编译器动态生成什么东西，效率很高，是为静态分配。） 这种使用traits的方式类似于Haskell种的type classes：

-- 限定了Printable的print_all
print_all :: (Printable t) => [t] -> IO ()
print_all xs = mapM_ my_print xs

-- 限定了Printable和Copy的print_all
-- 这里只写出函数签名，Copy在Haskell中无对应 
print_all :: (Printable t, Copy t) => [t] -> IO ()

6 Traits对象和动态方法分配

上述的方法使得我们能够定义具有多态行为的函数，该函数作用于被trait限定的未知类型。然而，考虑下面这个函数：

trait Drawable { fn draw(&self); }

fn draw_all(shapes: ~[T]) {
    for shapes.each |shape| { shape.draw(); }
}

我们可以在circles数组上调用draw_all，也可以在squares数组上调用draw_all（假定它们都实现了Drawable trait），但是不能在一个包含了circles和squares的数组上调用draw_all。如果我们需要这么做，那么可以把trait的名字当作类型，叫做object。

fn draw_all(shapes: &[@Drawable]) {
    for shapes.each |shape| { shape.draw(); }
}

在上例中，没有类型参数。取而代之的是，用@Drawable类型来表示任何实现了Drawable trait的managed box值。为了构造这样的值，我们可以使用as运算符来将一个值转换成一个object。

impl Circle: Drawable { fn draw(&self) { ... } }

impl Rectangle: Drawable { fn draw(&self) { ... } }

let c: @Circle = @new_circle();
let r: @Rectangle = @new_rectangle();
draw_all([c as @Drawable, r as @Drawable]);

这里省略了new_circle和new_rectangle的代码；假设它们返回缺省大小的CircleS和RectangleS。注意，和字符串及向量类似，objects具有动态大小，因此只能通过指针访问。将类型强转为traits时指针必须兼容，所以，不能把@Circle强转为~Drawable。

// A managed object
let boxy: @Drawable = @new_circle() as @Drawable;
// An owned object
let owny: ~Drawable = ~new_circle() as ~Drawable;
// A borrowed object
let stacky: &Drawable = &new_circle() as &Drawable;

在traits类型的对象上调用方法时使用的是动态分配。因为编译器编译时不知道调用哪个方法，而在运行时通过lookup table（也叫vtable或者dictionary）才知道调用哪个方法。 这种使用Traits的方式类似Java interfaces。

7 Trait 继承

我们可以声明一个trait继承自其他traits（supertraits，父trait），一个类型如果实现了一个trait，也必须同时实现它的supertraits。例如：我们定义一个Circle trait继承了Shape。

trait Shape { fn area(&self) -> float; }
trait Circle : Shape { fn radius(&self) -> float; }

现在，我们要用一个类型实现Circle，同时也必须实现Shape。

struct CircleStruct { center: Point, radius: float }
impl CircleStruct: Circle {
     fn radius(&self) -> float { sqrt(self.area() / pi) }
}
impl CircleStruct: Shape {
     fn area(&self) -> float { pi * square(self.radius) }
}   

注意，Circle的方法可以调用Shape的方法，比如我们的radius实现中调用了area方法。这种求圆半径的方法很蠢，纯粹用来帮我们明白继承的含义。 trait继承在Haskell对应的概念是subclassing。上述例子在Haskell中对应为：

class Shape a where
    area :: a -> Float
  
class (Shape a) => Circle a where
    getRadius :: a -> Float
  
data CircleStruct = CircleStruct { center :: Point
                                 , radius :: Float }  
                    
instance Circle CircleStruct where
    getRadius c = sqrt $ (area c) / pi
  
instance Shape CircleStruct where
    area c = pi * (radius c)^2

在具有类型参数的函数中，supertrait的方法可以被由subtrait（子trait）限定的参数类型的值调用。回到之前的例子：trait Circle : Shape。

fn radius_times_area(c: T) -> float {
    // `c` is both a Circle and a Shape
    c.radius() * c.area()
}

上述例子在Haskell中对应为：

radius_times_area :: (Circle t) => t -> Float
radius_times_area c = getRadius c * area c

类似的，supertrait方法也可以在trait object上调用。

let mycircle: Circle = @mycircle as @Circle;
let nonsense = mycircle.radius() * mycircle.area();

注意：上述trait objects相关的继承暂时未实现好。

 注： Rust的trait本质上类似Haskell的type class。但是混合了Java的interface特性，即trait可以当作类型使用，可以构造某个trait类型的对象。而这部分偏OO的能力在纯函数式的Haskell中没有对应。