04-类型系统的力量

类型系统的力量

原理

Rust 类型系统基石为 Hindley-Milner（HM）扩展版本，增加子类型（lifetime subtyping）、trait约束、关联类型。类型推导通过合一把类型变量与具体类型统一：Vec::<_> 遇到 push(42i32) 后合一 ?0 = i32。

Curry-Howard 同构：类型 = 命题，程序 = 证明：

逻辑	类型	Rust 示例
$(A\wedge B)$	积类型 (A, B)	(i32, String)
$(A\vee B)$	和类型	Result<T, E>
$(A\to B)$	函数 fn(A) -> B	fn f(x: i32) -> bool
$\forall x.P(x)$	多态 for<T>	fn foo<T>(x: T)
$\exists x.P(x)$	存在类型	dyn Trait
$\perp$ (假)	Never 类型	!
$\top$ (真)	Unit 类型	()

单态化：泛型代码在编译时为每个具体类型生成独立副本，无虚函数调用开销。这是零成本抽象的核心——与 C++ 模板的 monomorphization 同构，但 Rust 先完成类型检查再展开，错误信息更清晰。

---

语法

类型推导需显式标注的场景

let v: Vec<i32> = vec![];         // 必须标注 vec![] 无法推断元素类型
let x: i32 = "42".parse().unwrap(); // parse 需要目标类型

Never 类型 !

fn exit() -> ! { std::process::exit(1); }  // 永不返回
// ! 可强制转换为任何类型（类型系统的 ⊥ 特性）
 
let x: i32 = loop { break 42; };  // loop 可带 break 值

类型大小的”动态计算”

use std::mem;
println!("{}", mem::size_of_val(&[1, 2, 3])); // &[i32] = 16B (ptr+len)

关联类型（简化）

trait Iterator {
    type Item;  // 关联类型：每种迭代器指定产出类型
    fn next(&mut self) -> Option<Self::Item>;
}

Trait 对象类型擦除

let v: Vec<Box<dyn Display>> = vec![Box::new(1), Box::new("hi")];
// 运行时通过 vtable 找到 fmt 函数指针

---

实践

力扣问题

力扣: 力扣图最短路径题 — 泛型矩阵

AI 自检

1. fn foo<T: Display>(x: T) 中的 <T: Display> 在编译后如何表示？与 fn foo(x: &dyn Display) 的区别？
2. Rust 的 ! (Never) 类型对应 Curry-Howard 中的什么逻辑概念？