Возврат бесконечного цикла - PullRequest
Новая
       8

Возврат бесконечного цикла

1 голос
/ 13 января 2011

Это Упражнение 28.1.2 из HtDP . Я успешно реализовал функцию neighbors, и все тесты прошли успешно. 

(define Graph (list
               (list 'A (list 'B 'E))
               (list 'B (list 'E 'F))
               (list 'C (list 'D))
               (list 'D empty)
               (list 'E (list 'C 'F))
               (list 'F (list 'D 'G))
               (list 'G empty)))

(define (first-line n alist)
  (cond
    [(symbol=? (first alist) n) alist]
    [else empty]))

;; returns empty if node is not in graph
(define (neighbors n g)
  (cond
    [(empty? g) empty]
    [(cons? (first g)) 
     (cond
       [(symbol=? (first (first g)) n) (first-line n (first g))]
       [else (neighbors n (rest g))])]))

; test cases
(equal? (neighbors 'A Graph) (list 'A (list 'B 'E)))
(equal? (neighbors 'B Graph) (list 'B (list 'E 'F)))
(equal? (neighbors 'C Graph) (list 'C (list 'D)))
(equal? (neighbors 'D Graph) (list 'D empty))
(equal? (neighbors 'E Graph) (list 'E (list 'C 'F)))
(equal? (neighbors 'F Graph) (list 'F (list 'D 'G)))
(equal? (neighbors 'G Graph) (list 'G empty))
(equal? (neighbors 'H Graph) empty)

Проблема возникает, когда я копирую и вставляю код из Figure 77 текста. Предполагается определить, достижим ли узел назначения из исходного узла. Однако представляется, что код входит в бесконечный цикл, за исключением наиболее тривиального случая, когда узлы отправления и назначения совпадают. 

;; find-route : node node graph  ->  (listof node) or false
;; to create a path from origination to destination in G
;; if there is no path, the function produces false
(define (find-route origination destination G)
  (cond
    [(symbol=? origination destination) (list destination)]
    [else (local ((define possible-route 
            (find-route/list (neighbors origination G) destination G)))
        (cond
          [(boolean? possible-route) false]
          [else (cons origination possible-route)]))]))

;; find-route/list : (listof node) node graph  ->  (listof node) or false
;; to create a path from some node on lo-Os to D
;; if there is no path, the function produces false
(define (find-route/list lo-Os D G)
  (cond
    [(empty? lo-Os) false]
    [else (local ((define possible-route (find-route (first lo-Os) D G)))
        (cond
          [(boolean? possible-route) (find-route/list (rest lo-Os) D G)]
          [else possible-route]))]))

Проблема в моем коде? Спасибо.

1 Ответ

1 голос
/ 13 января 2011

ОК, проблема действительно заключается в моем собственном коде. Я должен был вернуть список, а не список, содержащий узел и соседние узлы. то есть (neighbor 'A Graph) должен производить (list 'B 'E), а не (list 'A (list 'B 'E)).

...