impl Trait

WARNING 个人学习笔记，感觉可能对别人有用，就发出来了（这个论坛不支持 LaTeX 我也很绝望啊），如果有更新，可能不会继续在这里修改了。如果有错误，请评论告诉我。 >_<

impl Trait 在 Rust 中实现了 extential types（ref）。

RFC

• 1522: Conservative impl Trait
• 1951: Expand impl Trait
• 2071: impl Trait type alias

历史

RFC 1522 最先提出了 impl Trait 的概念，但有如下限制：

1. 只用于函数和固有方法；
2. 只用于返回值。

RFC 1951 是 1522 的发展：

1. 确定了 impl Trait 语法，而不是 some/any；
2. 解决有关生命周期的问题；
3. 允许在参数位使用 impl Trait。

RFC 2071 进一步增加了创建 named existential types 的能力，允许在 let const static 中使用 impl Trait。

Rust 1.26 引入的 impl Trait 是 RFC 1522 和 1951，2071 尚未实现。

虽然我们说 Rust 的 impl Trait 实现了 existential type，但实际上 RFC 1951 也允许 impl Trait 用于 universal type。这主要是基于对称性的考虑（既然能用于返回值，也应该能用于参数）。

理论基础

impl Trait 实现了 existential type：

$$\exists x \lbrace a:x; P(x) \rbrace$$

和泛型的 universal type 相对：

$$\forall x \lbrace a:x; P(x) \rbrace $$

我们可以这样考虑：$\forall x. P(x)$ 意味着对于任一类型变元，我们都能找到一个类型 $P(x)$。这里 $P$ 是类型构造器。Universal type 可以看作类似函数的东西，扔进去一个类型，得到一个新类型。

而相比之下，$\exists x. P(x)$ 意味着我们有一个类型 $x$ 满足 $P(x)$，即 existential type 实际上是一个 pair $(x, P(x))$，对类型的使用者来说，他并不知道 $x$ 具体是什么，只知道满足这个关系。

于是很清楚地看到，existential type 和 universal type 实际上是对偶的关系：

1. existential type 减少了泛型，而 universal type 增加了泛型
2. existential type 把类型隐藏在了「右边」，而 universal type 里类型变元必须出现在「左边」

通过柯里化，可以把 $n+1$ 阶的 existential type 转换成 $n$ 阶的 universal type，例如： $$ (\exists x. P(x))\rightarrow y \implies \forall x.(P(x) \rightarrow y)$$

用法

Rust 1.26 要求 impl Trait 只用于函数和固有方法。不能用于 trait 的原因可能是 impl Trait 不代表一个固定类型，如果允许用于 trait 方法，则会泄漏抽象。

用于返回值

用于返回值是 impl Trait 最早提出的用法，即 existential type。impl Trait 的类型由函数编写者确定，这个类型是完全不透明的，只能让编译器推导。

fn get_adder(y: i32) -> impl Fn(i32) -> i32 {
    move |x| x+y
}

fn main() {
    // let 处不能使用 impl Trait
    let plus1 = get_adder(1);
    let plus2 = get_adder(2);
    println!("{} {}", plus1(1), plus2(1));
}

在函数和固有方法这里，impl Trait 可以完全当作已知的固定的一个类型，可以用于构成更复杂的类型。

fn get_adder(y: i32) -> (i32, impl Fn(i32) -> i32) {
    (y, move |x| x+y)
}

fn main() {
    let (_, f) = get_adder(1);
    assert_eq!(f(1), 2);
}

用于函数参数

用于函数参数是 RFC 1952 提出的扩展，实际上是 universal type。

// 新写法
fn apply(x: i32, f: impl Fn(i32) -> i32) -> i32 {
    f(x)
}

fn apply_old1<T: Fn(i32) -> i32>(x: i32, f: T) -> i32 {
    f(x)
}

fn apply_old2<T>(x: i32, f: T) -> i32
    where T: Fn(i32) -> i32
{
    f(x)
}

fn main() {
    let plus1 = |x: i32| x+1;
    println!("{}", apply(1, plus1));
    println!("{}", apply_old1(1, plus1));
    println!("{}", apply_old2(1, plus1));
}

但是，impl Trait 并没有引入一个类型变元名字，所以 scope 是怎样的是存疑的。Rust 编译器选择使每个 impl Trait 引入一个新类型变元。

trait Animal {}

struct Bird {}
struct Horse {}

impl Animal for Bird {}
impl Animal for Horse {}

fn foo1(x: &impl Animal, y: &impl Animal) {}
fn foo2<T1: Animal, T2: Animal>(x: &T1, y: &T2) {}
fn bar<T: Animal>(x: &T, y: &T) {}

fn main() {
    let tux = Bird{};
    let pony = Horse{};

    foo1(&tux, &pony);
    foo2(&tux, &pony);
    bar(&tux, &pony);
}

这里 foo1 和 foo2 是等价的，和 bar 不相同，因此编译器会对 bar 报错，因为 T 已经被绑定到 Bird 上了。

在特定场景下，这可能不是我们期望的行为（函数作者对传进来的具体类型很难进行控制），因此还是需要使用原来的写法。相反，这在函数返回值处并不是一个问题：因为每个 impl Trait 具体是什么类型，函数作者是非常清楚的。

universal return type

要深刻理解 impl Trait 的 existential type 特点，可以和放在返回值处的 universal type 相比。

fn universal_ret<T>() -> T;
fn existential_ret() -> impl Trait;

须注意，universal_ret 的 T 是由调用者给定的，而不是函数作者！因此，调用者对 T 究竟是什么有完全的把握，而函数作者一无所知。类型：$\forall T \left( \mathrm{unit} \rightarrow T\right)$。编译器可以把调用者处推导的类型与 T 合一，从而构造出一个具体的 universal_ret。

而后者 existential_ret 的返回值类型由函数作者给定，对类型是什么有完全的把握，用户只知道它满足 Trait 约束，对这个类型究竟是什么一无所知。类型：$\exists T(\mathrm{unit}\rightarrow T)$。

评价

impl Trait 使得 trait 更像一个具体的类型了。最重要的是，使得我们可以写出匿名类型的类型，从而消除装箱和动态分发的开销。