/** * This module defines a collection of generic one-pass traversals over * lists. * * The primitive term traversal operators of Strateg -- all, some, one -- * can be combined with the other control operators in a wide variety * of ways to define full term traversals. * */ module strategy/traversal/list imports strategy/conditional strategy/traversal/simple strategies /* Term traversals can be categorized into classes according to how much of the term they traverse and to which parts of the term they modify. \paragraph{Everywhere} The most general class of traversals visits every node of a term and applies a transformation to it. The following operators define traversals that apply a strategy \verb|s| to all nodes of a term. */ all-l(s) = ?[_|_] < [s | s] + all(s) topdown-l(s) = rec x(s; all-l(x)) bottomup-l(s) = rec x(all-l(x); s) downup-l(s) = rec x(s; all-l(x); s) downup-l(s1, s2) = rec x(s1; all-l(x); s2) downup2-l(s1, s2) = rec x(s1; all-l(x); s2) /* The traversals above go through all constructors. If it is not necessary to traverse the entire tree, the following versions of the traversals can be used. They are parameterized with a strategy operator \verb|stop| that */ topdownS-l(s, stop: (a -> a) * a -> a) = rec x(s; (stop(x) <+ all-l(x))) bottomupS-l(s, stop: (a -> a) * a -> a) = rec x((stop(x) <+ all-l(x)); s) downupS-l(s, stop: (a -> a) * a -> a) = rec x(s; (stop(x) <+ all-l(x)); s) downupS-l(s1, s2, stop: (a -> a) * a -> a) = rec x(s1; (stop(x) <+ all-l(x)); s2) /* A variation on bottomup is a traversal that also provides the original term as well as the term in which the direct subterms have been transformed. (also known as a paramorphism?) */ bottomup-para-l(s) = rec x(!(<id>, <all-l(x)>); s) /* \paragraph{Frontier} Find all topmost applications of \verb|s|; */ alltd-l(s) = rec x(s <+ all-l(x)) alldownup2-l(s1, s2) = rec x((s1 <+ all-l(x)); s2) alltd-fold-l(s1, s2) = rec x(s1 <+ all-l(x); s2)