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