[comp.lang.misc] iteration/traversion

gaynor@athos.rutgers.edu (Silver) (03/21/88)

F(Type) - The desired function to apply to elements of type.

iterator(Type) - a function that returns the next valid element of
		 Type according to some rule, if one exists; null
		 otherwise

traverser(Type) - a function that, for every iteration T of Type, F(T)
		  is evaluated

I suppose you can see what I'm getting at.  Supplying a function to
the traverser is equivalent to:

    while (T = iterator(Type)) do F(T)

This is easy enough to do in most programming languages.  Even pascal
allows you to pass subprograms to other subprograms.

I can't count the number of traversals I've written like this:

/****************************************************************\
* preorder: apply F to every subtree of T, ordered by a preorder *
*	    traversal						 *
\****************************************************************/
preorder(tree T, function F(tree))
  if T, F(T)
	preorder(left(T), F)
	preorder(right(T), F)
			     ___
		    Cheers,  \o/  Silver
      201-932-2443 (mostly)   V   (internet) gaynor@rutgers.edu
      201-545-0458 (rarely)  _|_  (uucp)     ...!rutgers!gaynor

daniels@teklds.TEK.COM (Scott Daniels) (03/22/88)

In article <Mar.20.14.47.03.1988.1079@athos.rutgers.edu> 
	gaynor@athos.rutgers.edu (Silver) writes (on iterators):
>F(Type) - The desired function to apply to elements of type.
>iterator(Type) - a function that returns the next valid element of
>	 Type according to some rule, if one exists; null otherwise
>traverser(Type) - a function that evaluates F(T), for every iteration of Type
>Supplying a function to the traverser is equivalent to:
>    while (T = iterator(Type)) do F(T)
>
In my experience of writing many similar functions, it helps to provide an
argument to pass along with the iterated type:

F(Type,Arg) - The desired function to apply to elements of type.
iterator(Type) - a function that returns the next valid element of
	 Type according to some rule, if one exists; null otherwise
traverser(Type,Arg) - a function that evaluates F(T,Arg), for every T
Supplying a function to the traverser is equivalent to:
	while (T = iterator(Type)) do F(T,Arg)

This allows one to avoid using globals to communicate with F (The arg can 
always be the address of a collection of information if more than one is 
needed)

>I can't count the number of traversals I've written like this:
>/****************************************************************\
>* preorder: apply F to every subtree of T, ordered by a preorder *
>*	    traversal						 *
>\****************************************************************/
>preorder(tree T, function F(tree))
>  if T, F(T)
>	preorder(left(T), F)
>	preorder(right(T), F)

/* preorder: apply F to every subtree of T, (preorder traversal) */
preorder( T, F, Arg )
 struct tree *T;
 void (*F)();
 void *Arg;
{
 for( ; NULL != T;T = T->right ) { F(T,Arg); preorder(T->left, F,Arg); }
}

/* preprint: print tree T in preorder to a file */
preprint( tree, file )
 FILE *f;
{
 void fprintNode();

 if( NULL == f ) f = stdout;
 preorder( T, fprintNode, f );
}

-Scott Daniels	(daniels@teklds.UUCP)