Boost logo

Boost :

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-02-27 14:38:56

On Fri, Feb 27, 2004 at 05:46:26PM -0000, Andy Little wrote:
> Thanks for the Examples. Apologies for not giving more constructive feedback
> on them. I will have to spend a lot more time reading the docs to understand
> all of it.... but I am getting an inkling of what the thing is about. Maybe
> if I had to manipulate generic trees I would be keener yet. Meanwhile I
> have spent some time on it but gradually got carried away with an expression
> tree. Somewhere in the FC++ Docs is a call for applications. A calculator
> ala C++3rd Ed examples might be just what is needed as a, less abstract yet,
> working example. This is my guess at one way the FP expression might
> look(Guessing from a quick look at Haskell):

[ ExprTree example elided ]

Well, I don't have time to code up a full/exciting example along these
lines right now, but perhaps you will enjoy the code below. Lemme know
if you think a more-fleshed-out version of this would be an interesting

The example makes simple "int" expression trees: there are 3 kinds of
expressions (Value, Plus, Negate). At the end I use a fold to create
two tree operations: eval() and pretty(). In main() I build this tree:
     / \
    5 -
and evaluate and print it.

#include <iostream>
using std::ostream;
using std::cout;
using std::endl;
#include <string>
using std::string;
#include <sstream>
using std::ostringstream;

#include "prelude.hpp"
#include "boost/tuple/tuple.hpp"

using namespace boost::fcpp;
using boost::shared_ptr;
using boost::tuple;
using boost::tuples::element;
using boost::get;
using boost::make_tuple;

struct Expr {
   virtual ~Expr() {}
typedef boost::shared_ptr<Expr> E;

struct Value : Expr {
   int x;
   Value( int x_ ) : x(x_) {}

struct Plus : Expr {
   E x;
   E y;
   Plus( E x_, E y_ ) : x(x_), y(y_) {}

struct Negate : Expr {
   E x;
   Negate( E x_ ) : x(x_) {}

struct FoldExpr {
   template <class Tup, class E> struct sig : public fun_type<
      typename RT<typename element<0,Tup>::type,int>::result_type> {};
   template <class V, class B, class U>
   typename sig<tuple<V,B,U>,E>::result_type
   operator()( const tuple<V,B,U>& ops, E e ) const {
      if( Value* v = dynamic_cast<Value*>(&*e) ) {
         return get<0>(ops)( v->x );
      if( Plus* p = dynamic_cast<Plus*>(&*e) ) {
         return get<1>(ops)( (*this)(ops,p->x), (*this)(ops,p->y) );
      if( Negate* n = dynamic_cast<Negate*>(&*e) ) {
         return get<2>(ops)( (*this)(ops,n->x) );
      throw "bad";
typedef full2<FoldExpr> fold_expr_type;
fold_expr_type fold_expr;

string int2string( int x ) {
   ostringstream oss;
   oss << x;
   return oss.str();

int main() {
   lambda_var<1> X;
   lambda_var<2> Y;

   E e( new Plus( E(new Value(5)), E(new Negate( E(new Value(3)) )) ) );

   fun1<E,int> eval = fold_expr( make_tuple( id, plus, negate ) );

   fun1<E,string> pretty = fold_expr( make_tuple(
     ,lambda(X,Y)[ X %plus% string("+") %plus% Y ]
     ,boost::fcpp::plus(string("-")) ) ); // darn ADL

   cout << eval(e) << endl;
   cout << pretty(e) << endl;

-Brian McNamara (lorgon_at_[hidden])

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