## 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.

Pages: 1 2

[…] 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.

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