Boost logo

Boost :

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-02-26 15:13:11

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_at_[hidden])

Boost list run by bdawes at, gregod at, cpdaniel at, john at