On Thu, Feb 26, 2004 at 02:39:40PM +0200, Peter Dimov wrote:
Brian McNamara wrote:
The FP programmer, being enamored with higher-order functions (HOFs), notices that all these tree functions have a common pattern. Rather than write tons of miscellaneous tree functions, he instead writes one function to do them all:
// using FC++ struct FoldTree { template <class L, class N, class SPT> struct sig : public fun_type<L> {}; template <class L, class N, class T> L operator()( const L& leaf, const N& node, shared_ptr<Tree<T> > t ) const { if( !t ) return leaf; else return node( t->data, (*this)(leaf,node,t->left), (*this)(leaf,node,t->right) );
The order of evaluation is unspecified, so if the subexpressions have side effects, the code is not portable. But the programmer wouldn't know it if it happens to work on the specific platform/compiler/version/moon phase.
Pure FP doesn't suffer from these problems, but C++ does. As a simple example, try to print a tree using fold_tree.
Yes. I think I mentioned it in an earlier message, but it bears repeating. When you use FP, HOFs make it harder to specify and reason about side-effects, and currying and lazy evaluation make it harder to specify and reason about object lifetimes. These are among the reasons the FP people usually go for purity.
With fold_tree(), it is easy to express new tree functions on the fly. For example, here is a function to get an inorder travseral:
fold_tree( fcpp::list<T>(), lambda(D,L,R)[ cat[ L, cons[D,R] ] ] )
You got me confused for a while with the omission of the third argument. I then spent a while trying to understand how the lambda thing would get passed around. ;-)
Oops! My bad. I'm actually trying to make the examples accessible, rather than inpenetrable. :) When you get accustommed to automatic currying, you don't ever notice that you're using it.
Anyway, the obvious question #1 is, of course, why should I use a fcpp::list instead of std::list,
Here the answer is because I'm building the the list "pure"ly, so fcpp::list is probably much more efficient (fcpp::cons is constant time, whereas the same operation on a std::list is potentially O(N)).
and obvious question #2 is why I should copy the tree into a list at all, when I could've just flattened it into a sequence with iterators. To be fair, you do point that out yourself.
Good point; I was just keeping the example simple. (In fact, when you use fcpp::lists with lazy evaluation, lists effectively become input iterators. It would be interesting to implement inorder-iterators for this tree both with and without FC++. Hmm. How easy/hard would it be to build bidirectional iterators for a tree like this? I've never tried. If you have the time to cook some up (using Boost), I would enjoy seeing them, and comparing them to whatever I could cook up with FC++.)
However iterators do avoid the unspecified traversal order problem. Not that you couldn't have created inorder_fold_tree, of course, but iterators make it much harder to accidentally leave the order unspecified.
Time out. This: fold_tree( fcpp::list<T>(), lambda(D,L,R)[ cat[ L, cons[D,R] ] ] ) always yields an inorder traversal. And: // preorder fold_tree( fcpp::list<T>(), lambda(D,L,R)[ cons[ D, cat[L,R] ] ] ) // reverse-inorder fold_tree( fcpp::list<T>(), lambda(D,L,R)[ cat[ R, cons[D,L] ] ] ) // etc. The lambda uses no effects, and thus the order of evaluation inside the fold_tree() doesn't matter.
fold_tree( 0, lambda(D,L,R)[ plus[ 1, max[L,R] ] ] )
Okay, but this is easy to do even with boost::bind. We want unique selling points. ;-)
I do see the smiley, but just to be abundantly clear, I was selling HOFs ("Here's an example that shows how higher-order functions are useful..."), and boost::bind is indeed just such an entity. -- -Brian McNamara (lorgon@cc.gatech.edu)