Rust 类型系统足以写出更简洁的代码

Rust 函数式编程 递归 类型系统 Rust 的类型系统就是你所需要的一切 Ein Monarch 8 分钟阅读· 12 小时前

写出地道的 Rust 代码并不是人人都具备的技能。不过别担心——你还是可以学会的。没错，你可以写出性能更好的代码，但更重要的是，写出更简洁的代码。 一般来说，Rust 程序员主要有两种类型；而这两种都是错的。让我用一个例子来演示。 我们的任务是求一棵二叉树的最大深度。 第一位程序员写下了这样的代码： pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { let mut stack = vec![(root, 0)]; //(node, current depth) let mut max_depth = -1; while let Some((node, depth)) = stack.pop() { match node { None => max_depth = std::cmp::max(max_depth, depth), Some(c) => { stack.push((c.borrow().left.clone(), depth+1)); stack.push((c.borrow().right.clone(), depth+1)); max_depth 这代码不能说错……但能算简洁吗？ 绝对不是。即便有 Rust 全部的语法糖——match 和 while-let——它依然冗长，难以快速浏览。 所有难以阅读的代码，其根源往往是命令式编程的使用。它写起来容易、执行起来也容易，但很少能带来好看的代码。 而 Rust——号称“支持多种范式”——也帮不上忙。一个人能使用多种范式，并不意味着对某项任务不存在客观上最佳的范式。 在这个例子中，正如在许多例子中一样，客观上最佳的范式是函数式编程。就拿 Haskell 举例：当你被限制只能用递归和一等函数时，你就被迫写出读起来像英语一样的代码。 我们的问题可以轻松地写成递归： MaxDepth(tree) = 1+max(MaxDepth(tree.left), MaxDepth(tree.right)) 我们用它来写一个函数式编程的解法： pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 { match root { None => 0, Some(r) => std::cmp::max( max_depth(r.borrow().left.clone()), max_depth(r.borrow().right.clone()) ) + 1 事实上，这正是第二位程序员会写出的代码。 它更易读，而且性能依然出色——时间复杂度是 O(节点数)，空间复杂度是 O(1)（只要你别想太多）。 这……这还不是纯函数式编程——它是受函数式编程启发的写法，可读性也因此受损。我是说，拜托——当它几乎逐字重复了两次 max_depth(r.borrow().left.clone()) 时，你真能说它简洁吗？ 而且它甚至不纯：每次调用 Rc.clone() 都有副作用（具体来说，是增加引用计数）。 我们无法在破损的画布上绘出杰作。我们需要从零开始，构建一个完美的解法。 Rust 的问题在于，你的程序所依赖的每一个资源都自带臃肿。即便是本该轻量的东西，比如 i32，也打包了边界检查和各种各样的内置函数——我们是高级开发者；我们不需要辅助轮。 所以让我们从一张白纸开始：单元结构体。 struct Zero; struct Succ<N>(N); 单元结构体就像幽灵。它们在编译时消失，不给我们带来任何开销：这就是 Rust 承诺的零成本抽象。 用两行代码，我们创造出了数字：

• Zero 表示 0
• Succ（Successor 的缩写）接受 N 并返回 N + 1 但等等，你喊道，有什么不对。结构体是类型，不是函数或值！你到底在说什么！？ 我看不出有什么不对。我是说，这在你眼里不像一个数字吗？ type One = Succ<Zero>; type Two = Succ<One>; //or Succ<Succ<Zero>> 但别太担心；毕竟，在函数式编程中，类型、函数和值之间真的有什么不同吗？只要代码正确且可读，又有什么关系呢？ 你说得对，但还有个问题：类型只存在于编译期。如果这些“数字”在执行时消失了，我们怎么用它们做任何事呢？ 记住，Rust 拥有强大的类型系统。 有时，在解释 Rust 时，人们会说 trait 就像接口。这种解释再错误不过了。 不；真正理解 Rust 的开发者知道，trait 是特定输入类型与输出类型之间的映射——基本上就是接受并返回类型的函数。 让我通过实现一个返回我们两个数字中较大者的 Max trait 来向你展示。 共有 4 种情况：
• Max(0,0)=0
• Max(N+1, 0)=N+1
• Max(0, N+1)=N+1
• Max(A+1, B+1)=Max(A,B)+1 这是成立的，因为我们只实现了 0 和 Succ；不可能输入负数，所以 A、B、N≥0。我们又一次看到了 Rust 类型系统的优雅：当我们自己定义事物时，需要处理的情况就更少。 你知道吗，我其实一直在考虑发起一项请愿，让 Rust 的类型系统成为世界第八大奇迹——如果你有兴趣签名，请告诉我。 代码简直就是用少量语法点缀的英语： trait Max<A, B> { type Output; impl Max<Zero,Zero> for () { type Output = Zero; impl<N> Max<Zero,Succ<N>> for () { type Output = Succ<N>; impl<N> Max<Succ<N>, Zero> for () { type Output = Succ<N>; impl<A,B, SubMax> Max<Succ<A>, Succ<B>> for () where (): Max<A,B, Output=SubMax> { type Output = Succ<SubMax>; 很美，不是吗？ 不过别分心，我们想要求一棵树的最大深度。 为此，我们首先需要一棵树。 struct Node<L, R>(L, R); struct Nil; 现在我们恰好拥有了我们需要的东西（而且只有我们需要的东西）。 数字、树，以及一个 max 函数，全都没有栈分配、堆分配和无用的函数栈帧……轻量而高效，正如万物本该如此。 一切都是不可变的，所以借用检查器不会在后面追着我们咬（反正它从来也没促使代码变得更简洁）。 我们终于把一切编织进一个 trait 中。 由前面的公式， MaxDepth(Tree) = Max(MaxDepth(Tree.Left), MaxDepth(Tree.Right))+1 trait MaxDepth<T> { type Output; impl MaxDepth<Nil> for () { type Output = Zero;

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）