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

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-02-25 23:22:01

On Wed, Feb 25, 2004 at 12:24:40PM -0500, Brian McNamara wrote:
> Objects are not anathema to FP.  (But _mutable_ objects are anathema in
> _pure_ FP.)  Both paradigms (OOP and FP) deal with both data and
> behavior.  In OOP, the data (objects) are the focus.  In FP, the
> behaviors (functions) are the focus.
> 
> 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...

Here's an example that shows how higher-order functions are useful,
especially when you want to do lots of different kinds of computations
on a particular object/datatype.  Hope you'll bear with me through the
example, even if it's a little trying at various points.  (I'm trying to
show both the "OOP" and the "FP" ways to approach a problem.)

Say you have a binary tree data structure:

   template <class T>
   struct Tree {
      typedef T value_type;
      T data;
      shared_ptr<Tree> left, right;
      Tree( const T& x, shared_ptr<Tree> l, shared_ptr<Tree> r )
         : data(x), left(l), right(r) {}
      Tree( const T& x ) : data(x), left(), right() {}
   };

There are various things you might want to do with the data in the tree.
For example, we might want to collect all the data into a "inorder
traversal" sequence.  One straightforward way to do this is: 

   // helper function, main function is below
   template <class T>
   void oop_tree_inorder( shared_ptr<Tree<T> > t, vector<T>& v ) {
      if(t) {
         oop_tree_inorder( t->left, v );
         v.push_back( t->data );
         oop_tree_inorder( t->right, v );
      }
   }
   template <class T>
   vector<T> oop_tree_inorder( shared_ptr<Tree<T> > t ) {
      vector<T> v;
      oop_tree_inorder( t, v );
      return v;
   }

and now we can call "oop_tree_inorder(a_tree)" and get back a vector
with all the data.

Another thing we might need to do with a binary tree is compute its
height.  So we may write:

   template <class T>
   int oop_tree_height( shared_ptr<Tree<T> > t ) {
      if( !t )
         return 0;
      else
         return 1+max( oop_tree_height(t->left), oop_tree_height(t->right) );
   }

Easy enough.  There are lots more things to do with trees.  If the Ts
are LessThanComparables, we might want to find the minimum element in
the tree.  Since the tree may be empty, a "tree_min" function should
return a maybe<T> (where a maybe<T> is either "nothing" or "just t"--
maybe is very similar to boost::optional).  As a convenience, I am
assuming that there already exists a function min_maybe:
   T min_maybe( T, maybe<T> );
which computes the minimum of a value and a maybe-value.  Anyway:

   template <class T>
   maybe<T> oop_tree_min( shared_ptr<Tree<T> > t ) {
      if( !t )
         return NOTHING;
      else
         return just( min_maybe( min_maybe( t->data, oop_tree_min(t->left) )
                               , oop_tree_min(t->right) ) );
   }

Or, if T is some arithmetic-like type, we may want to create a new tree,
where all the data have been incremented by a certain value.  Assuming
the existence of "mk_tree":
   shared_ptr<Tree<T> > 
   mk_tree( T, shared_ptr<Tree<T> >, shared_ptr<Tree<T> > );
then we could write:

   template <class T>
   shared_ptr<Tree<T> > oop_tree_add( shared_ptr<Tree<T> > t, const T& x ) {
      if( !t )
         return shared_ptr<Tree<T> >();
      else
         return mk_tree( t->data + x, oop_tree_add(t->left,x),
                                      oop_tree_add(t->right,x) );
   }

And there are tons of other things we might want to do with trees (sum
all the data in the tree, get a reverse-post-order traversal, ...).  We
could spend the afternoon writing tons of tree functions if we liked.
(But we probably wouldn't; the Tree class doesn't deserve such a wide
interface, filled with tons of only-occasionally-useful methods.)

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

If the tree is empty, we return an empty list.  Otherwise, we cons the
current node data (D) onto the right-recursive call (R), and then
concatenate the left-recursive call (L) onto the front.  What if we want
the height of a tree?

   fold_tree( 0, lambda(D,L,R)[ plus[ 1, max[L,R] ] ] )

The empty tree has height 0.  For non-empty trees, we add 1 to the max
of the recursive calls.  What about min?

   fold_tree( maybe<int>(),
              lambda(D,L,R)[ just[ min_maybe[min_maybe[D,L],R] ] ] )

Etc.  If we want new tree functions, fold_tree() lets us create them
on-the-fly as needed.  Of course, if you are going to be using a
specific function more than once, you would probably bind it to a name.  
For example, if you are going to be repeatedly asking the heights of
trees-of-characters, you would probably write

   boost::function< int(shared_ptr<Tree<char> >) > hgt = 
      fold_tree( 0, lambda(D,L,R)[ plus[ 1, max[L,R] ] ] )

and then just call "hgt(my_tree)" as necessary.

In fact, this is pretty similar to what already happens with iterators.
Back when I was writing all the simple-minded oop_tree_xxx() functions,
you were probably thinking to yourself that if _you_ were writing all
these algorithms to do stuff with tree data, you'd follow the lead of
the STL and create iterators for the tree class.  Then you could
decouple the algorithms from the data structure, and with just a few
different kinds of iterators (for pre/in/post-order), you could easily
use STL algorithms or iterator adapters to compose solutions to various
tree computations on-the-fly.

In this sense, HOFs and iterators (or iterator adapters) are very
similar.  The FPers will create _functions_ (like fold_tree) to abstract
away in order to create generalized algorithms, whereas the OOPers will
create _objects_ (like iterators) for the same general ends.  Both
strategies have the same general flavor, just taken with a different
tack.

Anyway, that's just one tiny (and thus a little contrived) example of
how HOFs can be useful when applied to OO data structures.  You are, of
course, probably already familiar with HOFs in some limited STL
domains: sort() takes a comparator, and transform() and for_each() take
functions as arguments.  When you have a decent framework for easily
creating little functions on-the-fly (like boost::lambda or FC++),
using HOFs becomes an increasingly attractive way to design general
algorithm interfaces.

-- 
-Brian McNamara (lorgon_at_[hidden])