带副作用的递归模式作者Marvin Borner2026 年 4 月 20 日。像 Haskell 这样的常见函数式编程语言会用递归模式泛化折叠/展开模式通常需无限递归类型和某种函子实例化概念。今天要展示一种带副作用的递归模式实现它利用将数据结构重新函数化为副作用和处理程序的方法。其实这篇文章更多是在展示副作用和处理程序而非递归模式本身。先构建一些基本的 lambda 项作为示例数据结构如恒等函数 λx.x 可编码为 Lam(x, Sym(x)).show。在 Effekt 中可通过匹配和递归调用遍历函数来遍历这些项。“范畴态射”catamorphism递归模式对折叠操作进行了泛化。范畴态射Catamorphism传统上会有一个单独的、参数化的 TermF其中 Term 的所有递归出现都被一个类型变量取代之前的 Term 类型变成无限递归类型但 Effekt 不支持无限类型。不过Effekt 支持副作用和处理程序Term 的重新函数化变体由特定接口定义。范畴态射的带副作用实现是 Term → TermF[A] 模式的泛化可将 pretty 函数重写为范畴态射还能使用 cata 计算 lambda 项的构造函数数量或返回项中的所有自由变量。参数态射Paramorphism与 cata 相比para 还会将原始数据结构传递给处理程序可通过扩展 cata 实现。例如在替换 t[x/r] 中可使用它防止递归进入正在被替换的项 t。余范畴态射Anamorphism余范畴态射主要是从单个种子展开结构与范畴态射相反。可将使用 emit 副作用生成自然数的程序泛化为用于列表构造的 ana 函数还可用于将使用德布鲁因索引 (DTerm) 的 lambda 项转换为 Term。混合态射Hylomorphism混合态射结合了范畴态射和余范畴态射将两者定义结合得到简单的 hylo。hyloNaive 先递归构造项再解构而 hylo 可以不构造额外 Term最终版本中 Term 完全消失。轮到你了现在轮到进一步探索这种递归模式的构造了如思考如何通过参数态射或混合态射实现阶乘如何在 Effekt 中定义“历史态射”histomorphism和“未来态射”futumorphism等。这里有[交互式游乐场](/playground)、[语言指南](/tour)和[安装说明](/docs)的链接。Effekt 语言由[Effekt 研究团队](https://se.cs.uni-tuebingen.de/group/)开发。