Breadth−First Traversal Via Staging

Abstract

An effectful traversal of a data structure iterates over every element, in some predetermined order, collecting computational effects in the process. Depth-first effectful traversal of a tree is straightforward to define in a compositional way, since it precisely follows the shape of the data. What about breadth-first effectful traversal? An indirect route is to factorize the data structure into shape (a structure of units) and contents (a vector of elements, in breadth-first order), traverse the vector, then rebuild the data structure with new contents. We show that this can instead be done directly, using staging. That staging is captured using a construction related to free applicative functors. Moreover, the staged traversals lend themselves well to fusion; we prove a novel fusion rule for effectful traversals, and use it in another solution to Bird's "repmin" problem.