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