#### Module 10

Last updated: Thu, 26 Mar 2015 13:23:36 -0400

##### Supplemental Materials
• Backtracking

• Here are some slides about searching via generative recursion.

Note: These slides are from a previous semester. We provide them because learning is often aided by looking at different presentations of the same material. However, previous iterations of the course had a different structure and different style requirements. Read these slides for their ideas only. When there are discrepancies, follow the rules of our current course.

##### Goals
• Understand the concept of backtracking and when and how to write backtracking functions.

• Understand how accumulators are also useful in generative recursive functions.

##### In-class

Revise find-path from Chapter 33 such that it always terminates. Be sure to state accumulator invariants and termination arguments as necessary.
 (require rackunit) (require racket/set) ; A Node is a Symbol ; Represents a vertex in a graph. ; A Path is a ListOf ; Represents a sequence of connected Nodes. ; A Graph is a ListOf<(cons Node ListOf)> ; A list of adjacency lists representing a directed graph. ; WHERE: (map first G) has no duplicates and represents the nodes in G ; and the rest of each adj list are the neighbors of the first node. (define SAMPLE-G '((A B E) (B E F) (C D) (D) (E C F) (F D G) (G))) ; get-nodes : Graph -> ListOf ; Returns the nodes in g. (define (get-nodes g) (map first g)) ; neighbors : Node Graph -> ListOf ; Returns a list of all nodes v such that G has edge u-v. (define (neighbors u G) (rest (assq u G))) ; find-path : Node Node Graph -> Maybe ; Finds a path from orig to dest in G, or #f if no such path exists. ; Strategy: ??? ; Termination argument: ??? (define (find-path orig dest G) (cond [(symbol=? orig dest) (list dest)] [else (local ((define next (neighbors orig G)) (define path/#f (find-path/list next dest G))) (if (false? path/#f) #f (cons orig path/#f)))])) ; find-path/list : ListOf Node Graph -> Maybe ; Finds a path from some node in origs to dest in G. ; Returns #f is there is no path from any node in origs to dest. ; Strategy: data decomposition on origs : ListOf (define (find-path/list origs dest G) (cond [(empty? origs) #f] [else (local ((define path/#f (find-path (first origs) dest G))) (if (false? path/#f) (find-path/list (rest origs) dest G) path/#f))])) (check-equal? (find-path 'C 'D SAMPLE-G) '(C D)) (check set-member? '((E F D) (E C D)) (find-path 'E 'D SAMPLE-G)) (check-false (find-path 'C 'G SAMPLE-G))
Notes:
• To help readability, use a /#f prefix for variables that represent Maybe<X> values.

• Inlining one decomposition of a Maybe<X> result is acceptable.

• From now on, you may require and use functions from racket/set if you wish.

1. Complete the design strategy and termination argument for find-path.

2. Implement the following list-processing function:
 ; find : (X -> Maybe) ListOf -> Maybe ; Returns (f x) for the first element x in lst where (f x) != #f, ; otherwise returns #f. (define (find f lst) ...)

3. Revise find-path to use find instead of find-path/list.

4. Revise find-path such that the following test case does not loop forever:
 (define CYCLIC-G '((A B E) (B E F) (C B) (D) (E C F) (F D G) (G))) (check set-member? '((B F D) (B E F D) (B E C D)) (find-path 'B 'D CYCLIC-G))
Be sure to state a proper invariant if you use an accumulator. Also, update the termination argument such that it explains why the function always terminates.

Problem Set 10