On Tue, Mar 02, 2004 at 09:33:40AM -0500, Gennadiy Rozental wrote:
if you could provide an examples of intended usage for this class to address real-life problems with performance comparison with corresponding imperative analog, that would be good enough to satisfy me on the topic.
Here is a quick example (based on an idea from an earlier thread) which you may or may not find interesting. The "problem" is to code up some const forward iterators for preorder/inorder traversals of this simple data structure: template <class T> struct Tree { typedef T value_type; T data; Tree<T>* left; Tree<T>* right; Tree( const T& d ) : data(d), left(0), right(0) {} }; Below, I code up the iterators using both a "standard" mechanism and using FC++ lazy lists. I have not tried to "hand optimize" either version. Both versions have a bit of boilerplate code associated with them. Right now I want to focus on just the core logic. With FC++, an inorder traversal basically looks like this: template <class T> list<T> operator()( Tree<T>* t ) const { if( !t ) return NIL; else return (*this)(t->left) ^cat^ cons( t->data, thunk1(*this,t->right) ); } That is, you recurse on the left child, and concatenate that with a (lazy) recursive call on the right child with the current data stuck on the front. Pretty simple. Without FC++, I used a stack to manage the traversal. (My code is actually based on some code Allan Odgaard sent me when the topic was mentioned in passing a few days ago.) Here is the corresponding code in the iterator class that does the "logic": T* current; std::stack<T*> backtrack; ... in_tree_iterator (T* startAt = 0) : current(startAt) { backtrack.push(0); if( current ) while( current->left ) backtrack.push(current), current=current->left; } ... in_tree_iterator& operator++ () { if(current->right) { current = current->right; while( current->left ) backtrack.push(current), current=current->left; } else { current = backtrack.top(); backtrack.pop(); } return *this; } I am not as confident that it is correct, but it seems to work. I think most people would agree that the FC++ solution is easier to understand. I think the FC++ way is also easier to modify. To make it a preorder traversal instead of inorder, I just change return (*this)(t->left) ^cat^ cons( t->data, thunk1(*this,t->right) ); to return cons( t->data, thunk1(*this,t->left) ) ^cat^ thunk1(*this,t->right); That is, I do "data left right" rather than "left data right". The corresponding change in the other version is not so simple or intuitive in my opinion; this code: in_tree_iterator (T* startAt = 0) : current(startAt) { backtrack.push(0); if( current ) while( current->left ) backtrack.push(current), current=current->left; } ... in_tree_iterator& operator++ () { if(current->right) { current = current->right; while( current->left ) backtrack.push(current), current=current->left; } else { current = backtrack.top(); backtrack.pop(); } return *this; } becomes pre_tree_iterator (T* startAt = 0) : current(startAt) { backtrack.push(0); } ... pre_tree_iterator& operator++ () { if(current->right) backtrack.push(current->right); if(!(current = current->left)) current = backtrack.top(), backtrack.pop(); return *this; } The moral I am trying to sell is that lazy evaluation here is a win for the programmer; the code is shorter and clearer. Of course, there's a catch: performance. The FC++ version runs about 3-4 slower than the other version. I think it's valuable to have the trade-off available, so that you can choose between raw performance and code that's easier to read/understand. Anyway, the program is below. Enjoy. ---------------------------------------------------------------------- #define BOOST_FCPP_ENABLE_LAMBDA #include "prelude.hpp" using namespace boost::fcpp; #include <iostream> using std::cin; using std::cout; using std::cerr; using std::endl; #include <stack> #include <algorithm> #include <iterator> template <class T> struct Tree { typedef T value_type; T data; Tree<T>* left; Tree<T>* right; Tree( const T& d ) : data(d), left(0), right(0) {} }; template <class T> void insert( Tree<T>*& root, const T& data ) { if( !root ) root = new Tree<T>(data); else if( data < root->data ) insert( root->left, data ); else insert( root->right, data ); } // Based on code from Allan Odgaard template <typename T> struct pre_tree_iterator : public std::iterator<std::forward_iterator_tag, typename T::value_type> { T* current; std::stack<T*> backtrack; pre_tree_iterator (T* startAt = 0) : current(startAt) { backtrack.push(0); } bool operator!= (pre_tree_iterator const& rhs) const { return current != rhs.current; } bool operator== (pre_tree_iterator const& rhs) const { return current == rhs.current; } typename T::value_type const& operator* () const { return current->data; } pre_tree_iterator& operator++ () { if(current->right) backtrack.push(current->right); if(!(current = current->left)) current = backtrack.top(), backtrack.pop(); return *this; } pre_tree_iterator operator++ (int) { pre_tree_iterator tmp(*this); ++(*this); return tmp; } }; // helper functions to create iterators template <class T> pre_tree_iterator< Tree<T> > pre_begin_tree (Tree<T>* tree) { return pre_tree_iterator< Tree<T> >(tree); } template <class T> pre_tree_iterator< Tree<T> > pre_end_tree (Tree<T>*) { return pre_tree_iterator< Tree<T> >(0); } template <typename T> struct in_tree_iterator : public std::iterator<std::forward_iterator_tag, typename T::value_type> { T* current; std::stack<T*> backtrack; in_tree_iterator (T* startAt = 0) : current(startAt) { backtrack.push(0); if( current ) while( current->left ) backtrack.push(current), current=current->left; } bool operator!= (in_tree_iterator const& rhs) const { return current != rhs.current; } bool operator== (in_tree_iterator const& rhs) const { return current == rhs.current; } typename T::value_type const& operator* () const { return current->data; } in_tree_iterator& operator++ () { if(current->right) { current = current->right; while( current->left ) backtrack.push(current), current=current->left; } else { current = backtrack.top(); backtrack.pop(); } return *this; } in_tree_iterator operator++ (int) { in_tree_iterator tmp(*this); ++(*this); return tmp; } }; // helper functions to create iterators template <class T> in_tree_iterator< Tree<T> > in_begin_tree (Tree<T>* tree) { return in_tree_iterator< Tree<T> >(tree); } template <class T> in_tree_iterator< Tree<T> > in_end_tree (Tree<T>*) { return in_tree_iterator< Tree<T> >(0); } // FC++ way struct PreFlatten { template <class TTP> struct sig : fun_type< list<typename std::iterator_traits<TTP>::value_type::value_type> > {}; template <class T> list<T> operator()( Tree<T>* t ) const { if( !t ) return NIL; else return cons( t->data, thunk1(*this,t->left) ) ^cat^ thunk1(*this,t->right); } } pre_flatten; struct InFlatten { template <class TTP> struct sig : fun_type< list<typename std::iterator_traits<TTP>::value_type::value_type> > {}; template <class T> list<T> operator()( Tree<T>* t ) const { if( !t ) return NIL; else return (*this)(t->left) ^cat^ cons( t->data, thunk1(*this,t->right) ); } } in_flatten; int main() { int MAX; cin >> MAX; int* a = new int[MAX]; for( int i=0; i<MAX; ++i ) a[i] = i; std::random_shuffle( a, a+MAX ); Tree<int>* tree = 0; for( int i=0; i<MAX; ++i ) insert( tree, a[i] ); { cerr << "pre_tree_iterator" << endl; Timer timer; // please use your own timing mechanism here pre_tree_iterator<Tree<int> > end = pre_end_tree(tree); for( pre_tree_iterator<Tree<int> > i = pre_begin_tree(tree); i != end; ++i ) cout << *i << " "; cout << endl; cerr << timer.ms_since_start() << endl; } { cerr << "pre_flatten" << endl; Timer timer; list<int> l = pre_flatten(tree); list<int>::iterator end = l.end(); for( list<int>::iterator i = l.begin(); i != end; ++i ) cout << *i << " "; cout << endl; while(l) l=tail(l); cerr << timer.ms_since_start() << endl; } { cerr << "in_flatten" << endl; Timer timer; list<int> l = in_flatten(tree); list<int>::iterator end = l.end(); for( list<int>::iterator i = l.begin(); i != end; ++i ) cout << *i << " "; cout << endl; while(l) l=tail(l); cerr << timer.ms_since_start() << endl; } { cerr << "in_tree_iterator" << endl; Timer timer; in_tree_iterator<Tree<int> > end = in_end_tree(tree); for( in_tree_iterator<Tree<int> > i = in_begin_tree(tree); i != end; ++i ) cout << *i << " "; cout << endl; cerr << timer.ms_since_start() << endl; } } ---------------------------------------------------------------------- -- -Brian McNamara (lorgon@cc.gatech.edu)