苏锦钿 余珊珊

(1.华南理工大学 计算机科学与工程学院，广东 广州 510640;2.广东药学院 医药信息工程学院，广东 广州 510006)

作为归纳数据类型［1］上最重要的一种计算模式，递归操作fold［2］在程序设计、推理、转换和优化等方面具有广泛的应用，并构成其他各种复杂的递归计算的基础，如原始递归、Course-of-Value 迭代、带参数的递归和累积递归等.但fold 一方面要求计算源中的元素必须具备相应的代数结构，无法包含额外的参数用于作为计算的输入;另一方面只适合于描述计算过程中所产生的确定性结果，无法包含其他各种计算副作用(如偏序、非确定性、异常、连续、交互式输入、交互式输出等).针对上述问题，Cockett 等最早在文献［3-4］中利用笛卡尔封闭范畴上的强函子提出了强范畴数据类型的概念，使得强归纳数据类型上的fold 可包含额外的参数，并将其作为函数式程序语言Charity 的基础.随后，Pardo［5-7］进一步对强归纳数据类型上带固定参数和累积参数的递归操作pfold 和afold 的范畴论性质及其计算律进行了分析.笔者在前期工作中也分析了强共归纳数据类型上带固定参数的共递归及其计算律［8-9］，并将其扩展到hylomorhpism 中［10］，同时还从双代数的角度探讨了归纳与共归纳数据类型、递归与共递归间的关系［11］.上述研究都是针对强归纳或强共归纳数据类型上的纯函数，没有考虑计算过程中可能产生的副作用.

Fokkinga［12］结合monads 及集合范畴上的正则函子提出任意数据类型上的monadic 射和fold.Hu等［13］进一步将Fokkinga 的研究扩展到任意……