Я начинаю набрасывать какой-то код -
(define (find t q) ;; find q in t
(path empty) ;; the return path will be a list, we'll start it off as an empty list
(if (empty? t) ;; fundamental laws: always check for empty list first
#f ;; if the tree is empty, there is nothing to find, we use #f to signal this
(if (eq? q (car t)) ;; otherwise we can check if the node matches q ...
;; wups we can't do eq? test yet, it's possible `(car t)` is a list of nodes
))
Как мне это увидеть? Я смотрю на наш список ввода -
(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))
- Мы всегда проверяем
empty? сначала
- Если список не пустой, мы знаем, что имеем:
- хотя бы один элемент,
(car tree)
- остальные элементы,
(cdr tree)
- Я визуализирую элементы внешнего списка; их всего три:
1(2 (3) (4))(5 (6 (7) (8)) (9))
- Первый элемент был
1, поэтому я подумал, что смогу достать eq? и проверить, соответствует ли он q сразу
- Я заметил, что второй элемент был другого типа . Интуитивно понятно, что мы не можем сопоставить один элемент со списком элементов, поэтому мы должны обработать
list? case до того, как попробуем eq?
Исправь мою бу бу -
(define (find t q)
(path empty)
(if (empty? t)
#f
(if (list? (car t))
;; when the node is a list of nodes
(if (eq? q (car t))
;; when the node matches q
;; when the node does not match q
)))
Свернуть цепочки if до cond для лучшей читаемости -
(define (find t q)
(path empty)
(cond ((empty? t)
#f)
((list? (car t))
;; when the node is a list of nodes
)
((eq? q (car t))
;; when the node matches q
)
(else
;; when the node does not match q
))
Код теперь более плоский и приятный для чтения. Некоторые из этих пробелов сложно заполнить, но меня тянет ко второму пробелу; когда q равно (car t), это означает, что мы нашли совпадение, и пришло время вернуть path -
(define (find t q)
(path empty)
(cond ((empty? t)
#f)
((list? (car t))
;; when the node is a list of nodes
;; we'll come back to this ...
)
((eq? q (car t))
(cons q path)) ;; return the path with the final node
(else
;; when the nodes does not match q
;; and save this for later too ...
))
Хорошо, это было не так уж плохо. Поэтому я проверил, когда (car t) соответствует q, теперь я должен сказать, что происходит, когда он не совпадает. Когда (car t) не совпадает, я добавлю его в path и каким-то образом проверю, соответствует ли q любому из дочерних узлов, (cdr t) -
(define (find t q)
(path empty)
(cond ((empty? t)
#f)
((list? (car t))
;; when node is a list of nodes
;; we'll come back to this ...
)
((eq? q (car t))
(cons q path))
(else
;; add the node to the path ...
(cons (car t) path)
;; check the node's children for a match
(find (cdr t) q)
;; this doesn't quite work ...
))
Я сталкиваюсь с ситуацией, когда нам нужно обновить path новым узлом, и мне нужно вызвать find, у которого нет параметра path. Чтобы исправить это, я ввел цикл, который позволяет нам повторно вычислять выражение с любыми указанными нами аргументами -
(define (find t q)
(let loop ;; lazily and sloppily insert a named loop
((path empty) ;; initialize the parameters that will change
(t t))
(cond ((empty? t) ;; the expression to repeat, (cond ...)
#f)
((list? (car t))
;; when the node is a list of nodes
)
((eq? q (car t))
(cons q path))
(else
(loop (cons (car t) path) ;; updated path
(cdr t)))) ;; updated tree
Предложение else научило меня сопоставлять дочерние узлы, представляющие собой список узлов. Это, безусловно, облегчит работу с последним пробелом в коде, что и нужно делать, когда узел представляет собой список узлов! -
(define (find t q)
(let loop
((path empty)
(t t))
(cond ((empty? t)
#f)
((list? (car t))
;; we could just recur the loop with
(loop path
(car t))
;; but what about (cdr t) in this case?
(loop path
(cdr t))
((eq? q (car t))
(cons q path))
(else
(loop (cons (car t) path)
(cdr t))))
Последняя проблема здесь - у меня есть два (2) списка для проверки; (car t) определяется как список, а (cdr t) - список. Я должен проверить их обоих. Простое решение - объединить два loop вызова с or. Если один loop вернет #f, другой будет проверен -
(define (find t q)
(let loop
((path empty)
(t t))
(cond ((empty? t)
#f)
((list? (car t))
(or (loop path ;; or represents dysjunction!
(car t))
(loop path
(cdr t))))
((eq? q (car t))
(cons q path))
(else
(loop (cons (car t) path)
(cdr t))))
Исправить скобки, запустить автоматический индентор -
(define (find t q)
(let loop
((path empty)
(t t))
(cond ((empty? t)
#f)
((list? (car t))
(or (loop path
(car t))
(loop path
(cdr t))))
((eq? q (car t))
(cons q path))
(else
(loop (cons (car t) path)
(cdr t))))))
(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))
(find tree 4)
;; '(4 2 1)
(find tree 8)
;; (8 6 5 1)
(find tree 9)
;; (9 5 1)
Заметьте, что результат обратный, потому что действительно path построен в обратном порядке. Условие выхода, которое возвращает путь, просто требует вызова reverse перед возвратом -
(define (find t q)
(let loop
((path empty)
(t t))
(cond ((empty? t)
#f)
((list? (car t))
(or (loop path
(car t))
(loop path
(cdr t))))
((eq? q (car t))
(reverse (cons q path))) ;; don't forget to reverse!
(else
(loop (cons (car t) path)
(cdr t))))))
(define tree '(1 (2 (3) (4)) (5 (6 (7) (8)) (9))))
(find tree 4)
;; '(1 2 4)
(find tree 8)
;; (1 5 6 8)
(find tree 9)
;; (1 5 9)