Re: [boost] Re: Re: Re: Re: full functoids

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])