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

From: Peter Dimov (pdimov_at_[hidden])
Date: 2004-02-26 07:39:40

Brian McNamara wrote:
>> A lot of this discussion may be "too abstract" to be useful.  To make
>> things more concrete, in a little while I will post a short example
>> illustrating some differences of how the paradigms deal with data and
>> behaviors.
>
> Ok, as promised...

Nice example!

> 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.

>       }
>    };
>    typedef full3<FoldTree> fold_tree_type;
>    fold_tree_type fold_tree;
>
> fold_tree() captures the common essence of all of the tree functions
> we already wrote.  These algorithms all handle the empty tree case by
> returning some value, and for non-empty trees, the algorithms recurse
> on
> the left and right children, and combine the results with the data in
> the current node.  In fold_tree(), "leaf" is the value to be returned
> for empty trees, and "node" is a ternary function for combining the
> data with the recursive calls on the left and right children.
>
> 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. ;-)

Anyway, the obvious question #1 is, of course, why should I use a fcpp::list
instead of std::list, 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. 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.

>    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. ;-)