Franklyn Turbak and J. B. Wells.
Cycle Therapy: A Prescription for Fold and Unfold on Regular Trees.
Third International Conference on
Principles and Practice of Declarative Programming. ACM, 2001.
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.
[PS] [PDF]