Home Original page

Python from Wise Guy's Viewpoint

Brian McNamara! gt5163b at prism.gatech.edu
Sat Oct 25 20:21:38 EDT 2003 
prunesquallor at comcast.net once said:
>I think I have a stumper.  I'll be impressed if a type checker can
>validate this.  The same-fringe function takes a pair of arbitrary
>trees and lazily determines if they have the same leaf elements in the
>same order.  Computation stops as soon as a difference is found so
>that if one of the trees is infinite, it won't cause divergence.

Laziness is pretty orthogonal to static typing.

This one is so easy, we do it in C++ just for spite.  :)
I'm using the FC++ library as a helper.

----------------------------------------------------------------------
#include <iostream>
using std::ostream;
using std::cout;
using std::endl;

#include "prelude.hpp"
using namespace boost::fcpp;

struct LispCons;
typedef either<int,LispCons*> LispValue;

struct LispCons {
   LispValue car;
   LispValue cdr;
   LispCons( LispValue x, LispValue y ) : car(x), cdr(y) {}
};

LispValue make( int x )       { return inl(x); }
LispValue make( LispCons* x ) { return inr(x); }

// "l" prefix for "Lisp"
LispValue lnil = make( (LispCons*)0 );
LispValue lcons( LispValue x, LispValue y ) {
   return make( new LispCons( x, y ) );
}

ostream& operator<<( ostream& o, LispValue l ) {
   if( l.is_left() )
      o << l.left();
   else {
      LispCons* p = l.right();
      if( !p )
         o << "()";
      else
         o << "(" << p->car << "." << p->cdr << ")";
   }
   return o;
}

struct Fringe : public c_fun_type<LispValue,list<int> > {
   list<int> operator()( LispValue lv ) const {
      if( lv.is_left() )
         return cons( lv.left(), NIL );
      else {
         LispCons* lc = lv.right();
         if( lc==0 )
            return NIL;
         else
            return cat( Fringe()(lc->car),
                        thunk1(Fringe(),lc->cdr) );
      }
   }
} fringe;

int main() {
   LispValue one = make(1), two = make(2), 
             three = make(3), four = make(4);
   // tree1 = '((1 2) (3 (4))) 
   LispValue tree1 = lcons(lcons(one,lcons(two,lnil)), 
                        lcons(three,lcons(lcons(four,lnil),lnil)));
   cout << "tree1 is " << tree1 << endl;

   // tree2 = '(1 (2 3) (4))))
   LispValue tree2 = lcons(one,lcons(lcons(two,lcons(three,lnil)), 
                        lcons(lcons(four,lnil),lnil)));
   cout << "tree2 is " << tree2 << endl;

   cout << "fringe(tree1) is " << fringe(tree1) << endl;
   cout << "fringe(tree2) is " << fringe(tree2) << endl;

   LispCons* tmp = new LispCons(three,lnil);
   tmp->cdr = make(tmp);
   LispValue circle = make(tmp);
   cout << "first 10 of fringe(circle) is " 
        << take(10,fringe(circle)) << endl;

   // tree3 = '(1 (2 3) (<circle>))))
   LispValue tree3 = lcons(one,lcons(lcons(two,lcons(three,lnil)), 
                        lcons(lcons(circle,lnil),lnil)));
   cout << "first 10 of fringe(tree3) is " 
        << take(10,fringe(tree3)) << endl;
   cout << "tree2 = tree3? " << (fringe(tree2) == fringe(tree3)) << endl;
   
   return 0;
}
----------------------------------------------------------------------

The output:
----------------------------------------------------------------------
tree1 is ((1.(2.())).(3.((4.()).())))
tree2 is (1.((2.(3.())).((4.()).())))
fringe(tree1) is [1,2,3,4]
fringe(tree2) is [1,2,3,4]
first 10 of fringe(circle) is [3,3,3,3,3,3,3,3,3,3]
first 10 of fringe(tree3) is [1,2,3,3,3,3,3,3,3,3]
tree2 = tree3? 0
----------------------------------------------------------------------

-- 
 Brian M. McNamara   lorgon at acm.org  :  I am a parsing fool!
   ** Reduce - Reuse - Recycle **    :  (Where's my medication? ;) )
More information about the Python-list mailing list