J. Gibbons, and G. Jones. Proceedings of the third ACM SIGPLAN international conference on Functional programming - ICFP '98, page 273--279. New York, ACM Press, (1998)
DOI: 10.1145/289423.289455
Abstract
Folds are appreciated by functional programmers. Their dual, unfolds, are not new, but they are not nearly as well appreciated. We believe they deserve better. To illustrate, we present (indeed, we calculate) a number of algorithms for computing the breadth-first traversal of a tree. We specify breadth-first traversal in terms of level-order traversal, which we characterize first as a fold. The presentation as a fold is simple, but it is inefficient, and removing the inefficiency makes it no longer a fold. We calculate a characterization as an unfold from the characterization as a fold; this unfold is equally clear, but more efficient. We also calculate a characterization of breadth-first traversal directly as an unfold; this turns out to be the 'standard' queue-based algorithm.
%0 Conference Paper
%1 Gibbons1998UnderAppreciated
%A Gibbons, Jeremy
%A Jones, Geraint
%B Proceedings of the third ACM SIGPLAN international conference on Functional programming - ICFP '98
%C New York
%D 1998
%I ACM Press
%K 18-04-category-theory-explicit-machine-computation-and-programs 68n18-functional-programming-and-lambda-calculus haskell
%P 273--279
%R 10.1145/289423.289455
%T The Under-Appreciated Unfold
%U http://dx.doi.org/10.1145/289423.289455
%X Folds are appreciated by functional programmers. Their dual, unfolds, are not new, but they are not nearly as well appreciated. We believe they deserve better. To illustrate, we present (indeed, we calculate) a number of algorithms for computing the breadth-first traversal of a tree. We specify breadth-first traversal in terms of level-order traversal, which we characterize first as a fold. The presentation as a fold is simple, but it is inefficient, and removing the inefficiency makes it no longer a fold. We calculate a characterization as an unfold from the characterization as a fold; this unfold is equally clear, but more efficient. We also calculate a characterization of breadth-first traversal directly as an unfold; this turns out to be the 'standard' queue-based algorithm.
%@ 1581130244
@inproceedings{Gibbons1998UnderAppreciated,
abstract = {{Folds are appreciated by functional programmers. Their dual, unfolds, are not new, but they are not nearly as well appreciated. We believe they deserve better. To illustrate, we present (indeed, we calculate) a number of algorithms for computing the breadth-first traversal of a tree. We specify breadth-first traversal in terms of level-order traversal, which we characterize first as a fold. The presentation as a fold is simple, but it is inefficient, and removing the inefficiency makes it no longer a fold. We calculate a characterization as an unfold from the characterization as a fold; this unfold is equally clear, but more efficient. We also calculate a characterization of breadth-first traversal directly as an unfold; this turns out to be the 'standard' queue-based algorithm.}},
added-at = {2019-03-01T00:11:50.000+0100},
address = {New York},
author = {Gibbons, Jeremy and Jones, Geraint},
biburl = {https://www.bibsonomy.org/bibtex/2efa8964161f4b3111a785daf3854c2eb/gdmcbain},
booktitle = {Proceedings of the third ACM SIGPLAN international conference on Functional programming - ICFP '98},
citeulike-article-id = {1087941},
citeulike-attachment-1 = {gibbons_98_under.pdf; /pdf/user/gdmcbain/article/1087941/1120782/gibbons_98_under.pdf; f420ab81821b70f6afdb64fd1acec0dea259a0b9},
citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=289455},
citeulike-linkout-1 = {http://dx.doi.org/10.1145/289423.289455},
doi = {10.1145/289423.289455},
file = {gibbons_98_under.pdf},
interhash = {a9ebf650987135f37826d38c1c825b85},
intrahash = {efa8964161f4b3111a785daf3854c2eb},
isbn = {1581130244},
keywords = {18-04-category-theory-explicit-machine-computation-and-programs 68n18-functional-programming-and-lambda-calculus haskell},
location = {Baltimore, Maryland},
pages = {273--279},
posted-at = {2017-10-17 23:18:09},
priority = {5},
publisher = {ACM Press},
timestamp = {2019-03-01T00:11:50.000+0100},
title = {{The Under-Appreciated Unfold}},
url = {http://dx.doi.org/10.1145/289423.289455},
year = 1998
}