Practical example: Searching a binary tree

Lecture overview -- Keyboard shortcut: 'u'

Previous page: Practical example: Length of an improper list -- Keyboard shortcut: 'p'

Next page: Continuation Passing Style [Section] -- Keyboard shortcut: 'n'

Lecture notes - all slides and notes together

Lecture 3 - Page 31 : 43

Programming Paradigms
Simulation of other Paradigms and Continuations

Practical example: Searching a binary tree

Searching a binary tree involves a recursively defined tree traversal.

If we find the node we are looking for it is convenient to throw the node out of the tree traversal.

Notice the slightly 'imperative style' in find-in-tree below.

(define (find-in-tree tree pred)
 (call-with-current-continuation
  (lambda (found)
   (letrec
    ((find-in-tree1
       (lambda (tree pred)
            (if (pred tree)
                (found tree)
                (let ((subtrees (subtree-list tree)))
                   (for-each
                      (lambda (subtree) (find-in-tree1 subtree pred))
                      subtrees)))
            #f)))
    (find-in-tree1 tree pred)))  ))

A tree search function which uses a continuation found if we find what we search for. Notice that this examples requires the function subtree-list, in order to work. The function returns #f in case we do not find node we are looking for. Notice that it makes sense in this example to have both the if expression and the #f value in sequence!

Coroutines

We will see more examples of continuation programming in the lecture about 'Simulation of Other Paradigms in Scheme': Coroutines