文档教程【免费下载链接】patternsA catalogue of Rust design patterns, anti-patterns and idioms项目地址https://gitcode.com/gh_mirrors/pa/patterns点击查看免费下载本文基于 Rust Design Patternspatterns仓库中 Creational 模式分类 下的 Fold 模式文档 展开。Fold 模式的核心思想是对数据集合中的每个节点运行同一套算法把这些节点的折叠结果组合起来生成一个全新的数据结构。它解决的是复杂数据结构如抽象语法树 AST的整体改写与翻译问题是编译器中类型擦除、降级lowering等变换的经典实现范式。读完本文你将掌握 Folder trait 的抽象写法、遍历与操作分离的设计思路以及 Box/借用/Rc 三种所有权策略在效率与可复用性之间的权衡。什么是 Fold 模式Fold 模式的定义非常精炼对一个数据集合中的每一项运行算法以产生一个新的项从而构造出一个全新的集合。这里的集合不局限于线性容器它更常指树形的递归数据结构。模式的关键在于遍历逻辑如何递归访问子节点被抽象成 trait 的默认方法每个节点的具体变换逻辑对节点做什么由 trait 的实现者提供遍历与操作分离二者互不耦合可以独立演进。这与面向对象世界里常见的原地修改思路截然相反Fold 不修改旧结构而是通过逐层折叠出新的子节点自底向上拼装出一棵全新的树。从分类上看Fold 被归入 Creational 模式创建型与 Builder 模式 并列因为它本质上是一种用旧结构物造出新结构物的构造机制。二者的区别在于Builder 通过链式调用逐步配置字段而 Fold 通过递归折叠节点来构造。词源与命名争议文档作者坦承一个有趣的观察fold 与 folder 这两个词在 Rust 编译器rustc内部被大量使用但从语义上看rustc 中的 folder 更像 map映射而不是传统意义上的 fold归约。在函数式编程传统中fold也叫 reduce、accumulate指的是把集合归约成一个值例如求和(1..11).fold(0, |a, b| a b)得到 55。这一点在仓库的 函数式编程范式文档 中有非常直观的逐行推演表。而本模式中的 fold 指的反而是把一棵树映射成另一棵树语义上更接近 map。术语的错位是历史遗留读者不必纠结只需要知道本模式讨论的是结构到结构的递归映射而不是值到值的归约。核心示例用 Folder trait 重写 AST原文档给出了一个完整的、可运行的骨架示例原文标注rust,ignore需自行补全它演示了最典型的应用场景——对抽象语法树AST做整体变换。第一步定义将被折叠的 AST// The data we will fold, a simple AST. mod ast { pub enum Stmt { Expr(BoxExpr), Let(BoxName, BoxExpr), } pub struct Name { value: String, } pub enum Expr { IntLit(i64), Add(BoxExpr, BoxExpr), Sub(BoxExpr, BoxExpr), } }这是一棵典型的三层递归结构Stmt语句是顶层节点有两种形态表达式语句Expr以及绑定语句Let把名字与表达式绑定Expr表达式是递归核心可以是整数字面量IntLit也可以是二元运算Add/Sub运算的两个操作数又是BoxExpr由此形成任意深度的树Name是叶子节点仅含一个String。注意所有递归引用都通过Box包裹。Box是堆上独占所有权unique ownership的智能指针它让递归类型成为可能Rust 中直接内嵌递归枚举会导致无限大小编译错误也决定了后面所有权策略讨论的基调。第二步抽象 Folder trait——把遍历固化为默认方法// The abstract folder mod fold { use ast::*; pub trait Folder { // A leaf node just returns the node itself. In some cases, we can do this // to inner nodes too. fn fold_name(mut self, n: BoxName) - BoxName { n } // Create a new inner node by folding its children. fn fold_stmt(mut self, s: BoxStmt) - BoxStmt { match *s { Stmt::Expr(e) Box::new(Stmt::Expr(self.fold_expr(e))), Stmt::Let(n, e) Box::new(Stmt::Let(self.fold_name(n), self.fold_expr(e))), } } fn fold_expr(mut self, e: BoxExpr) - BoxExpr { ... } } }这个 trait 是整篇模式的核心请仔细读它的结构每个节点类型对应一个fold_*方法fold_name、fold_stmt、fold_expr。方法名即约定实现者必须为想变换的节点覆写对应方法。叶子节点默认原样返回fold_name默认直接把n还回去不做任何事。这是默认实现的意义所在——实现者只关心自己感兴趣的节点。内部节点默认递归遍历子节点fold_stmt默认实现先对子节点调用self.fold_expr(...)、self.fold_name(...),再用折叠后的子节点Box::new重新拼出新的Stmt。遍历逻辑被固化在这里与具体操作彻底分离。方法签名统一为mut self加上BoxT - BoxT。mut self意味着 Folder 可以携带跨节点的状态见下文输入输出都是Box保证了节点在折叠过程中所有权全程清晰转移。补全fold_expr的默认实现原文档以...省略逻辑与fold_stmt同理fn fold_expr(mut self, e: BoxExpr) - BoxExpr { match *e { Expr::IntLit(n) Box::new(Expr::IntLit(n)), Expr::Add(lhs, rhs) Box::new(Expr::Add(self.fold_expr(lhs), self.fold_expr(rhs))), Expr::Sub(lhs, rhs) Box::new(Expr::Sub(self.fold_expr(lhs), self.fold_expr(rhs))), } }第三步具体实现——把每个名字改成 foouse fold::*; use ast::*; // An example concrete implementation - renames every name to foo. struct Renamer; impl Folder for Renamer { fn fold_name(mut self, n: BoxName) - BoxName { Box::new(Name { value: foo.to_owned() }) } // Use the default methods for the other nodes. }实现者只需要覆写fold_name一个方法无条件构造一个新Name其value恒为foo。fold_stmt、fold_expr全部沿用默认遍历实现。对一棵 AST 运行Renamer的结果是得到一棵与旧 AST 结构完全一致、但每个名字都被替换成foo的新 AST。旧树没有被修改——它在折叠过程中被消费所有权转移新树是逐步重组出来的。这就是 Fold 模式的威力实现一个变换往往只需覆写一个方法其余结构代码全部复用 trait 默认实现。状态跨节点的信息传递真实的 Folder 几乎必然携带状态。文档明确指出A real life folder might have some state preserved between nodes in the struct itself.由于 trait 方法签名是mut selfFolder 实现者可以在结构体里保存任意字段并在遍历过程中读取、修改例如一个统计 AST 深度的 Folder在fold_stmt入口记录当前深度递归子节点时递增例如一个符号收集器在fold_name里把每个名字压入一个VecString例如一个上下文敏感的改写器根据祖先节点的信息决定当前节点如何变换。这正是本模式区别于纯函数式map的关键能力——后面的节点可以受前面节点处理结果的影响因为所有折叠都发生在同一个mut self上。不止是改写把一种结构折叠成另一种结构Fold 并不局限于同构改写。文档强调A folder can also be defined to map one data structure to a different (but usually similar) data structure. For example, we could fold an AST into a HIR tree (HIR stands for high-level intermediate representation).同一套Folder抽象只要改变各fold_*方法的返回类型与构造逻辑就能完成结构间的翻译。最经典的例子就是编译器前端把高层的 AST 折叠降级成 HIR高级中间表示再进一步折叠成 MIR、LLVM IR。每一步都是消费一棵树、产出一棵新树只是树中节点的长相变了。这就是 rustc 内部把这类组件命名为Folder的直接原因。动机什么时候该用 Fold 而不是 map文档给出了清晰的选择准则For simple operations on simple data structures, this can be done usingIterator::map. For more complex operations, perhaps where earlier nodes can affect the operation on later nodes, or where iteration over the data structure is non-trivial, using the fold pattern is more appropriate.简单的数据 简单的操作→ 用Iterator::map就够了。线性容器上的逐元素映射是它的主场。复杂的递归结构树→ 迭代器无法直接遍历非线性的树形结构遍历本身就是难点这正是 Fold 的默认递归实现要解决的。节点间存在依赖前一个节点影响后一个节点的处理→map的闭包是无状态的无法天然携带跨元素状态Fold 通过mut self天然支持。需要把一种结构翻译成另一种结构→map只改变元素不改结构形态Fold 可以整体重组。另外与 Visitor 模式 一样Fold 实现了遍历逻辑与逐节点操作的解耦遍历固化在 trait 默认方法里操作交给实现者。这保证了同一棵数据结构的多种不同变换可以并存而无需修改数据结构本身的定义。深入讨论所有权策略的三方权衡Fold 模式最微妙的设计点是fold_*方法以什么形式接受节点。文档给出了三种方案各有鲜明的效率与复用性权衡节点所有权形式原结构可否复用未变更节点是否需克隆其他代价BoxT独占所有权否原结构被消费否未变节点可直接复用原结构不能再被使用借用引用T是原结构可继续用是每个节点都要 cloneclone 开销可能昂贵引用计数RcT是否未变节点共享引用使用不顺手结构不可变方案一独占Box示例采用fn fold_expr(mut self, e: BoxExpr) - BoxExpr { ... }优点Box独占数据所有权折叠过程中如果某个节点没有变化可以直接把整个子树原样复用零拷贝开销。缺点输入输出都转移所有权原数据结构的原始副本在折叠后不复存在——你得到的是新树旧树已被消费。方案二借用引用如果让方法接受BoxT借用并返回BoxT原数据结构就能在折叠后继续存活。但代价是即使节点没有变化也必须为其 clone 一份数据因为输出必须拥有所有权而借用不能转移所有权。对深层大树来说clone 整棵树的成本可能高得难以接受。方案三RcT引用计数fn fold_name(mut self, n: RcName) - RcName { n }Rc号称两全其美原结构可以继续复用Rc::clone只递增引用计数未变更的节点也不必深拷贝直接共享Rc。但它有三个现实代价使用不顺手解引用、比较、模式匹配都要经过Rc写起来比Box/借用繁琐结构不可变Rc只提供共享只读访问想要mut得用RefCell做内部可变性进一步增加复杂度引用计数有运行时开销每个 clone/drop 都伴随原子操作Rc用非原子计数多线程则需Arc。因此文档的结论是这是一个在效率与可复用性之间可调校的旋钮项目里应结合树的规模、变换频率、是否需要保留原始结构来具体决策。从源码结构看本仓库示例选择Box正是因为编译器场景中旧树让位于新树是常态独占所有权换取的是最干净的拷贝语义与最优的未变子树复用。与 Visitor 模式的关系Visitor 模式 与 Fold 是姊妹模式仓库中两篇文档互相引用。它们的共同点都是行走数据结构、对每个节点执行操作、且把遍历与操作分离。Visitor 的 trait 方法签名是fn visit_name(mut self, n: Name) - T用借用遍历用返回值或()做计算。两者的根本差异在于对数据结构的处置方式维度FoldVisitor数据所有权消费输入产出新结构借用输入不改变数据遍历实现trait 默认方法递归拼装新节点独立的walk_*函数或accept方法典型返回值新结构BoxT/T计算值如i64或副作用数据结构结局新树诞生旧树被消费原树保持不变在 visitor.md 的示例 中Visitori64实现者把 AST 解释成整数值visit_expr直接返回n、lhs rhs等计算结果全程借用、不产生新结构。而本模式的Renamer则必然产出一棵新的 AST。选型口诀只读计算、不改变树 → Visitor要把树变成另一棵树 → Fold。与迭代器fold/map的关系文档在 See also 中特意澄清了一个常见混淆点Iterators have afoldmethod, however this folds a data structure into a value, rather than into a new data structure. An iteratorsmapis more like this fold pattern.迭代器Iterator::fold(init, f)把集合归约成一个值sum、product、min 等是函数式意义上的 fold迭代器Iterator::map(f)把一个集合映射成另一个集合元素类型可变语义上反而与本模式更接近——本模式本质就是树上的 map。仓库 paradigms.md 给出了迭代器 fold 的经典对比例子// Imperative let mut sum 0; for i in 1..11 { sum i; } println!({sum}); // Declarative println!({}, (1..11).fold(0, |a, b| a b));声明式写法用fold(0, |a, b| a b)一行完成求和并附有完整的逐轮演算表。对比可见迭代器 fold 是把线性结构 → 标量值而本模式是把树结构 → 树结构二者除了共享 fold 这个名字外并不等价。在其他语言如 Haskell中fold 通常就是指迭代器那种归约语义因此阅读 Rust 生态中把结构变换称为 fold 的代码时需要特别留意语境。总结Fold 模式是 Rust 中处理递归数据结构变换的标准答案其要点可归纳为结构自描述为每个节点类型定义一个fold_*方法叶子节点默认原样返回内部节点默认递归折叠子节点并重组——遍历逻辑一次写好处处复用操作即覆写具体变换只需覆写感兴趣的方法其余全部沿用默认实现代码量极小状态随身带mut self让 Folder 天然支持跨节点状态实现上下文敏感的复杂改写结构可翻译同一抽象既能同构改写也能把一种树AST折叠成另一种树HIR所有权可调校Box换效率、借用换保留、Rc兼得二者但牺牲易用性与可变性需按场景取舍。如需进一步对照学习可继续阅读仓库内的 Visitor 模式只读遍历的对照实现、Builder 模式同为创建型模式的结构构造思路以及 函数式编程范式迭代器 fold 的声明式归约推演。赞分享文档教程【免费下载链接】patternsA catalogue of Rust design patterns, anti-patterns and idioms项目地址https://gitcode.com/gh_mirrors/pa/patterns点击查看免费下载相关推荐PaperBanana贡献指南如何参与开源项目开发与社区协作PaperBanana贡献指南如何参与开源项目开发与社区协作 PaperBanana是一个为AI科学家自动化学术插图生成的开源项目它通过多智能体框架将原始科人工智能大模型AI Agent多智能体媒体生成AI 应用Dolibarr ERP CRM版本升级实战5个关键决策点确保平滑过渡Dolibarr ERP CRM版本升级实战5个关键决策点确保平滑过渡 Dolibarr ERP CRM作为开源的企业资源规划和客户关系管理一体化解决方案版企业应用后端如何使用m4b-tool从安装到高级操作的完整教程如何使用m4b tool从安装到高级操作的完整教程 m4b tool是一款强大的命令行工具专为合并、分割有声书文件如mp3、ogg、flac、m4a或m4音视频上一篇MemOS memos-local-plugin 服务端安全不变量解析无框架 HTTP SSE 服务器的 11 条守则下一篇【亲测免费】 推荐文章CBconvert - 漫画转换的终极工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考