Prev Up Next
A more involved example of continuation usage is the
problem of determining if two trees (arbitrarily nested
dotted pairs) have the same fringe, ie, the
same elements (or leaves) in the same sequence.
Eg,
(same-fringe? '(1 (2 3)) '((1 2) 3))
=> #t
(same-fringe? '(1 2 3) '(1 (3 2)))
=> #f
The purely functional approach is to flatten both trees
and check if the results match.
(define same-fringe?
(lambda (tree1 tree2)
(let loop ((ftree1 (flatten tree1))
(ftree2 (flatten tree2)))
(cond ((and (null? ftree1) (null? ftree2)) #t)
((or (null? ftree1) (null? ftree2)) #f)
((eqv? (car ftree1) (car ftree2))
(loop (cdr ftree1) (cdr ftree2)))
(else #f)))))
(define flatten
(lambda (tree)
(cond ((null? tree) '())
((pair? (car tree))
(append (flatten (car tree))
(flatten (cdr tree))))
(else
(cons (car tree)
(flatten (cdr tree)))))))
However, this traverses the trees completely to flatten
them, and then again till it finds non-matching
elements. Furthermore, even the best flattening
algorithms will require conses equal to the total
number of leaves. (Destructively modifying the input
trees is not an option.)
We can use call/cc to solve the problem without
needless traversal and without any consing. Each
tree is mapped to a generator, a procedure with
internal state that successively produces the leaves of
the tree in the left-to-right order that they occur in
the tree.
(define tree->generator
(lambda (tree)
(let ((caller '*))
(letrec
((generate-leaves
(lambda ()
(let loop ((tree tree))
(cond ((null? tree) 'skip)
((pair? tree)
(loop (car tree))
(loop (cdr tree)))
(else
(call/cc
(lambda (rest-of-tree)
(set! generate-leaves
(lambda ()
(rest-of-tree 'resume)))
(caller tree))))))
(caller '()))))
(lambda ()
(call/cc
(lambda (k)
(set! caller k)
(generate-leaves))))))))
When a generator created by tree->generator is
called, it will store the continuation of its call in
caller, so that it can know who to send the leaf to
when it finds it. It then calls an internal procedure
called generate-leaves which runs a loop traversing
the tree from left to right. When the loop encounters
a leaf, it will use caller to return the leaf as
the generator's result, but it will remember to store
the rest of the loop (captured as a call/cc
continuation) in the generate-leaves variable. The
next time the generator is called, the loop is resumed
where it left off so it can hunt for the next leaf.
Note that the last thing generate-leaves does,
after the loop is done, is to return the empty list to
the
caller. Since the empty list is not a valid leaf
value, we can use it to tell that the generator has
no more leaves to generate.
The procedure same-fringe? maps each of its tree
arguments to a generator, and then calls these two
generators alternately. It announces failure as soon
as two non-matching leaves are found:
(define same-fringe?
(lambda (tree1 tree2)
(let ((gen1 (tree->generator tree1))
(gen2 (tree->generator tree2)))
(let loop ()
(let ((leaf1 (gen1))
(leaf2 (gen2)))
(if (eqv? leaf1 leaf2)
(if (null? leaf1) #t (loop))
#f))))))
It is easy to see that the trees are traversed at most
once, and in case of mismatch, the traversals extend
only upto the leftmost mismatch. cons is not used.
Prev Up Next