Contractive Functions on Infinite Data Structures
Contractive Functions on Infinite Data Structures
复制标题
无限数据结构上的收缩函数
DOI：
10.1145/3064899.3064900
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Capretta V
中科院分区：
文献类型：
--
作者：
Capretta V
共归纳数据结构，如流或无限树，在函数式编程和类型论中有许多应用，并且自然地使用递归方程定义。但是，我们如何确保这样的方程是有意义的，即它们实际上生成了一个生产性的无限对象？实现生产力的标准方法是使用Banach不动点定理，该定理保证在一定条件下度量空间上递归方程解的唯一存在性。满足这些条件的函数称为压缩函数。本文以完备表示定理的形式给出了流上压缩的一个新的刻画，并将这一结果推广到一类非良基结构，首先推广到无限二叉树，然后推广到容器函子的最终余代数.这些结果在函数程序设计中有重要的潜在应用.其中，共归纳和共递归被成功地部署到连续反应系统、动态交互、信号处理和其他需要灵活操纵非良基数据的任务的建模中。我们的表示定理提供了一个定义的范例，以companitary计算这样的数据，很容易对他们的原因。
Coinductive data structures, such as streams or infinite trees, have many applications in functional programming and type theory, and are naturally defined using recursive equations. But how do we ensure that such equations make sense, i.e. that they actually generate a productive infinite object? A standard means to achieve productivity is to use Banach's fixed-point theorem, which guarantees the unique existence of solutions to recursive equations on metric spaces under certain conditions. Functions satisfying these conditions are called contractions. In this article, we give a new characterization of contractions on streams in the form of a sound and complete representation theorem, and generalize this result to a wide class of non-well-founded structures, first to infinite binary trees, then to final coalgebras of container functors.These results have important potential applications in functional programming, where coinduction and corecursion are successfully deployed to model continuous reactive systems, dynamic interactivity, signal processing, and other tasks that require flexible manipulation of non-well-founded data. Our representation theorems provide a definition paradigm to compactly compute with such data and easily reason about them.
登录
查看更多内容
具有共同模式的有根据的递归：终止和生产力的统一方法
DOI：
--
发表时间：
2013
期刊：
ACM SIGPLAN International Conference on Functional Programming
影响因子：
--
作者：
Andreas Abel;B. Pientka
通讯作者：
B. Pientka
作为共归纳模态的常识
DOI：
--
发表时间：
2007
期刊：
影响因子：
--
作者：
Venanzio Capretta
通讯作者：
Venanzio Capretta
嵌套不动点的近似 - 参数数据类型的代数视图
DOI：
--
发表时间：
2015
期刊：
Conference on Algebra and Coalgebra in Computer Science
影响因子：
--
作者：
A. Kurz;Alberto Pardo;Daniela Petrisan;P. Severi;F. D. Vries
通讯作者：
F. D. Vries
DOI：
10.1016/j.tcs.2009.10.014
发表时间：
2007
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
J. Endrullis;C. Grabmayer;D. Hendriks;Ariya Isihara;J. Klop
通讯作者：
J. Klop
最终余代数上的连续函数
影响因子：
0.3
作者：
Neil Ghani;P. Hancock;D. Pattinson
通讯作者：
D. Pattinson