Catamorphism

定义 Definition

catamorphism（折叠/归约映射）：在函数式编程与范畴论中，指一种把递归数据结构（如列表、树）按其结构“向下分解并汇总”为一个结果的通用模式；常见实现就是 fold（如 foldr/foldl）。它通常对应于某个初始代数（initial algebra）上的唯一同态，用来把结构化数据“折叠”成单一值或更简单的结构。
（该词在其他学科中偶有用法，但最常见的是计算机科学语境。）

发音 Pronunciation (IPA)

/ˌkætəˈmɔːrˌfɪzəm/

例句 Examples

A catamorphism can sum a list into a single number.
catamorphism 可以把一个列表求和并折叠成一个数字。

In functional programming, a catamorphism over an expression tree evaluates each node and combines the results according to the algebra, guaranteeing a well-structured recursion scheme.
在函数式编程中，对表达式树做 catamorphism 会逐节点求值，并按给定代数把结果组合起来，从而保证递归模式清晰且可控。

词源 Etymology

来自希腊语构词：**cata-**（向下、沿着）+ -morphism（形态变化/映射，源自 morphē “形态”）。字面含义可理解为“向下进行的结构映射”，契合其“沿数据结构递归并归约”的含义。

相关词 Related Words

• Fold
• Recursion
• Algebra
• Homomorphism
• Functor
• Fixpoint
• Anamorphism
• Hylomorphism

文学与著作中的用例 Literary Works

• Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire（Meijer, Fokkinga, Paterson）：以递归方案系统化介绍 catamorphism 等概念的经典论文。
• Category Theory for Programmers（Bartosz Milewski）：在用范畴论解释编程抽象时讨论 catamorphism（折叠）及相关递归方案。
• Categories for the Working Mathematician（Saunders Mac Lane）：虽更偏数学，但在范畴论语境中涉及（同态、初始代数等）为理解 catamorphism 提供理论背景的内容。