Thumbnail
Access Restriction
Subscribed

Author Gibbons, Jeremy ♦ Jones, Geraint
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Fold ♦ Unfold ♦ Co-induction ♦ Level-order ♦ Breadth-first ♦ Traversal ♦ Anamorphism ♦ Functional programing ♦ Program calculation
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.
Description Affiliation: School of Computing and Math. Sciences, Oxford Brookes University, Gipsy Lane, Headington, Oxford 0X3 OBP, UK (Gibbons, Jeremy) || Oxford University Computing Lab, Wolfson Building, Parks Road, Oxford OX1 3QD, UK (Jones, Geraint)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1983-05-01
Publisher Place New York
Journal ACM SIGPLAN Notices (SIGP)
Volume Number 34
Issue Number 1
Page Count 7
Starting Page 273
Ending Page 279


Open content in new tab

   Open content in new tab
Source: ACM Digital Library