一种带参数的Hylomorphisms及其计算律  

Hylomorphisms with Parameters and Its Associated Calculational Laws

作　　者：余珊珊[1] 李师贤[1] 苏锦钿[2] 

机构地区：[1]中山大学信息科学与技术学院 [2]华南理工大学计算机科学与工程学院

出　　处：《计算机研究与发展》2013年第3期602-618,共17页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(61103039);2010年高等学校博士学科点专项科研基金项目(20100172120043)

摘　　要：针对函数式程序语言中的一般hylomorphisms无法描述带参数的递归计算的问题,利用完全偏序范畴上的多项式函子分别给出带固定参数和累积参数的hylomorphisms——phylo射和ahylo射,证明了它们在固定参数和累积参数下都是唯一的,从而将Pardo对带参数的递归计算pfold和afold的研究扩展到hylomorphisms中,使得在hylomorphisms中可以直接包含额外的参数用于作为计算的输入或者保存临时的累积计算结果;从范畴论的角度分析了phylo射和ahylo射与其他各种递归及共递归之间的关系及其计算律,并利用函数程序语言Haskell给出相应的实现.Hylomorphisms in functional programming languages have the disadvantages of describing those recursive functions with parameters. To solve this problem, we use the polynomial functors defined on the category of completed partial orders to propose two different kinds of hylomorphisms with fixed or accumulating parameters, named phylo or ahylo morphisms respectively;and prove that they are both unique under the conditions of fixed or accumulating parameters, which as a result extends the research work of Pardo on recursive functions with parameters, named pfold and afold respectively, to hylomorphisms with parameters. Our work can allow hylomorphisms to directly carry extra parameters as the inputs of calculations or to store those accumulating values produced by programs temporally during the calculations. We also point out and analyze the relations of phylo morphisms and ahylo morphisms with other recursive and corecursive functions, and present their associated calculational laws in a categorical and abstract sense. Most of our work is implemented using the functional programming language Haskell.

关 键 词：递归 共递归 hylomorphisms 累积计算 代数 共代数 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]