Cycle therapy: a prescription for fold and unfold on regular trees
Cycle therapy: a prescription for fold and unfold on regular trees
复制标题
自行车疗法：在普通树木上折叠和展开的处方
DOI：
10.1145/773184.773200
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
J. Wells
中科院分区：
文献类型：
--
作者：
F. Turbak;J. Wells
在声明性编程语言中创建和操作循环数据结构可能很棘手。在声明性设置中，查看循环结构的自然方式是表示常规树，这些树可能是无限的，但只有有限数量的不同子树。本文展示了如何以 eager 和惰性语言实现展开（变形）运算符，以便在结果是常规树而不是无限惰性结构时创建循环结构。当在任何无限树上与严格组合函数一起使用时，通常的折叠（变形）运算符会产生未定义的结果。作为替代方案，本文定义并展示了如何在与表示常规树的循环结构上的严格函数一起使用时实现具有更有用语义的循环运算符。本文还引入了一种抽象数据类型（cycamores），以简化在急切语言和惰性语言中表示常规树的循环结构的使用。介绍了 cycamores 在 SML 和 Haskell 中的实现。
Cyclic data structures can be tricky to create and manipulate in declarative programming languages. In a declarative setting, a natural way to view cyclic structures is as denoting regular trees, those trees which may be infinite but have only a finite number of distinct subtrees. This paper shows how to implement the unfold (anamorphism) operator in both eager and lazy languages so as to create cyclic structures when the result is a regular tree as opposed to merely infinite lazy structures. The usual fold (catamorphism) operator when used with a strict combining function on any infinite tree yields an undefined result. As an alternative, this paper defines and show how to implement a cycfold operator with more useful semantics when used with a strict function on cyclic structures representing regular trees. This paper also introduces an abstract data type (cycamores) to simplify the use of cyclic structures representing regular trees in both eager and lazy languages. Implementions of cycamores in both SML and Haskell are presented.