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)