How to keep your neighbours in order
How to keep your neighbours in order
复制标题
如何维持邻居秩序
DOI：
10.1145/2692915.2628163
复制
发表时间：
2014
影响因子：
--
通讯作者：
McBride C
中科院分区：
文献类型：
--
作者：
McBride C
我提出了一种递归容器类型的数据类型通用处理方法，其元素保证以递增顺序存储，并系统地推出排序不变式。区间、列表和二叉搜索树是通用处理的实例。在接受这种治疗的过程中，我报告了各种失败的实验以及它们引发的可转移的学习经验。我证明了总元素排序足以提供插入和展平算法，并表明（注意类型的制定）实现保持如常。 Agda 的实例参数和模式同义词最大限度地提高了类型检查器进行的证明搜索，并最大限度地减少了程序文本中证明的出现，通常甚至完全消除了它们。推广到索引递归容器类型，除了排序之外，还可以表达诸如大小和平衡之类的不变量。举例来说，我实现了 2-3 棵树的插入和删除，通过类型检查的规则确保顺序和平衡。
I present a datatype-generic treatment of recursive container types whose elements are guaranteed to be stored in increasing order, with the ordering invariant rolled out systematically. Intervals, lists and binary search trees are instances of the generic treatment. On the journey to this treatment, I report a variety of failed experiments and the transferable learning experiences they triggered. I demonstrate that atotalelement ordering is enough to deliver insertion and flattening algorithms, and show that (with care about the formulation of the types) the implementations remain as usual. Agda'sinstance argumentsandpattern synonymsmaximize the proof search done by the typechecker and minimize the appearance of proofs in program text, often eradicating them entirely. Generalizing to indexed recursive container types, invariants such assizeandbalancecan be expressed in addition toordering. By way of example, I implement insertion and deletion for 2-3 trees, ensuring both order and balance by the discipline of type checking.
登录
查看更多内容
具有类型的红黑树
影响因子：
1.1
作者：
Stefan Kahrs
通讯作者：
Stefan Kahrs
精炼感应类型
DOI：
--
发表时间：
2012
期刊：
Log. Methods Comput. Sci.
影响因子：
--
作者：
R. Atkey;Patricia Johann;Neil Ghani
通讯作者：
Neil Ghani
Hasochism：依赖类型 Haskell 编程的快乐和痛苦
DOI：
--
发表时间：
2013
期刊：
ACM SIGPLAN Symposium/Workshop on Haskell
影响因子：
--
作者：
S. Lindley;Conor McBride
通讯作者：
Conor McBride
DOI：
--
发表时间：
1987
期刊：
影响因子：
--
作者：
P. Wadler
通讯作者：
P. Wadler
通过结构归纳证明程序的性质
DOI：
--
发表时间：
1969
期刊：
Computer/law journal
影响因子：
--
作者：
R. Burstall
通讯作者：
R. Burstall