Carl Hewitt’s Same-Fringe Problem
August 3, 2010
There are several ways to attack this problem. In some languages, you may want to use generators or iterators; one possibility in Scheme is to use continuations to capture the state of a scan through the tree, so that the computation can be resumed. However, the simplest approach is to use lazy lists (Scheme calls them streams), which are provided by a standard library called SRFI-41 Streams.
We begin by solving the problem the wrong way, flattening the two input trees to lists and comparing the lists for equality:
(define (flatten tree)
(cond ((null? tree) '())
((pair? (car tree))
(append (flatten (car tree))
(flatten (cdr tree))))
(else (cons (car tree)
(flatten (cdr tree))))))
This flatten function is nearly the same as the one in the Standard Prelude. Then it is easy to test two trees for equality:
(define (same-fringe? tree1 tree2)
(equal? (flatten tree1) (flatten tree2)))
This works, but violates the terms of the problem. The solution is to use streams. Here is a stream version of flatten, which is identical to the flatten shown above except that it forms the tree into a stream instead of a list:
(define-stream (flatten tree)
(cond ((null? tree) stream-null)
((pair? (car tree))
(stream-append
(flatten (car tree))
(flatten (cdr tree))))
(else (stream-cons
(car tree)
(flatten (cdr tree))))))
Then same-fringe? calls stream-equal? instead of equal? to compare the two streams, generating only as much of the stream as is necessary to determine if they are the same:
(define (same-fringe? eql? tree1 tree2)
(stream-equal? = (flatten tree1) (flatten tree2)))
Here’s an example:
> (same-fringe? = '(1 (2 3)) '((1 2) 3))
#t
You can run the program at http://programmingpraxis.codepad.org/ZNuaLYqQ, which includes all the streams machinery from SRFI-41.
Programming Praxis 
[…] Praxis – Carl Hewitt’s Same-Fringe Problem By Remco Niemeijer In today’s Programming Praxis exercise we have to implement Carl Hewitt’s same-fringe algorithm, which […]
My Haskell solution (see http://bonsaicode.wordpress.com/2010/08/03/programming-praxis-carl-hewitt%E2%80%99s-same-fringe-problem/ for a version with comments):
Here’s a Python solution using generators. Just for grins, I implemented seqsamefringe, which compares an arbitrary number of trees. Because cons cell is not a primitive type in Python, I implemented that, too.
#!/usr/bin/python from itertools import izip_longest # requires Python 2.6 # Define a tree/node class. class Node: def __init__(self, left, right): self.left = left self.right = right def __str__(self): return "(%s %s)" % (str(self.left), str(self.right)) def is_leaf(tree): return not isinstance(tree, Node) ###### samefringe ###### def samefringe(tree1, tree2): class uniq: pass # unique object g1 = leaves(tree1) g2 = leaves(tree2) return all(l1 == l2 for (l1, l2) in izip_longest(g1, g2, fillvalue=uniq)) def leaves(tree): if is_leaf(tree): yield tree else: for leaf in leaves(tree.left): yield leaf for leaf in leaves(tree.right): yield leaf # Compare a sequence of trees' fringes. def seqsamefringe(*trees): class uniq: pass return all(all(ls[0] == l for l in ls) for ls in izip_longest(*(leaves(tree) for tree in trees), fillvalue=uniq))Bug in your solution.
> (define (same-fringe? eql? tree1 tree2)
> (stream-equal? = (flatten tree1) (flatten tree1)))
should be
(stream-equal? = (flatten tree1) (flatten tree2))
Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.
You might be interested in the solution in scriptJ(TM) at
http://arxiv4.library.cornell.edu/abs/1008.2748v1
Cheers,
Carl
Carl,
Thanks for the link. And thanks for visiting my corner of the web.
Phil