带副作用的递归模式
作者：Marvin Borner，2026 年 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/)开发。
