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.

About these ads

Pages: 1 2

7 Responses to “Carl Hewitt’s Same-Fringe Problem”

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

  2. Remco Niemeijer said

    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):

    data Tree a = Node (Tree a) (Tree a) | Leaf a
    
    flatten :: Tree a -> [a]
    flatten (Node l r) = flatten l ++ flatten r
    flatten (Leaf x)   = [x]
    
    sameFringe :: Eq a => Tree a -> Tree a -> Bool
    sameFringe a b = flatten a == flatten b
    
  3. kbob said

    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))
    
  4. Kanak Kshetri said

    Bug in your solution.

    > (define (same-fringe? eql? tree1 tree2)
    > (stream-equal? = (flatten tree1) (flatten tree1)))

    should be
    (stream-equal? = (flatten tree1) (flatten tree2))

  5. programmingpraxis said

    Oooh, that’s embarrassing. Fixed. Thanks for pointing it out.

  6. You might be interested in the solution in scriptJ(TM) at

    http://arxiv4.library.cornell.edu/abs/1008.2748v1

    Cheers,
    Carl

  7. programmingpraxis said

    Carl,

    Thanks for the link. And thanks for visiting my corner of the web.

    Phil

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 643 other followers

%d bloggers like this: