| The Under-Appreciated Unfold (1998) | |||||||||||||||||||
Abstract | |||||||||||||||||||
| Folds are appreciated by functional programmers; the benefits of encapsulating common patterns of computation as higher-order operators are well-known and well understood. Their dual, unfolds, are nearly as well-known, but 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. Keywords: Program calculation, functional programming, fold, unfold, anamorphism, ... | |||||||||||||||||||
Publication details | |||||||||||||||||||
| |||||||||||||||||||