/**
 * 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)