Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space)
Revisiting catamorphisms over datatypes with embedded functions (or, programs from outer space)
复制标题
重新审视具有嵌入式函数（或来自外太空的程序）的数据类型的变形
DOI：
--
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
T. Sheard
中科院分区：
文献类型：
--
作者：
L. Fegaras;T. Sheard
我们回顾了Paterson和Meijer&Hutton的工作，其中描述了如何为嵌入被定义类型的逆变量出现的递归数据类型定义构造逆变形。它们的构造要求，对于每一次变质作用，都需要定义一种与该变质作用具有相反关系的变质作用。我们提出了一种替代结构，它用更宽松的限制取代了严格的要求，即为每个变质作用定义一个逆变形作用。由此得到的结构比Paterson，Meijer和Hutton的结构具有更有效的实现，并且相关的限制可以通过Hindley-Milner类型的推理算法来实施。我们提供了大量的例子来说明我们的方法。
We revisit the work of Paterson and of Meijer & Hutton, which describes how to construct catamorphisms for recursive datatype definitions that embed contravariant occurrences of the type being defined. Their construction requires, for each catamorphism, the definition of an anamorphism that has an inverse-like relationship to that catamorphism. We present an alternative construction, which replaces the stringent requirement that an inverse anamorphism be defined for each catamorphism with a more lenient restriction. The resulting construction has a more efficient implementation than that of Paterson, Meijer, and Hutton and the relevant restriction can be enforced by a Hindley-Milner type inference algorithm. We provide numerous examples illustrating our method.