Этот вопрос является продолжением Как мне получить поддерево по индексу ?. Этот вопрос касается индексации в глубину (для которой я предоставил решение в стиле передачи продолжения в глубину). Этот вопрос здесь касается индексации в ширину и, в частности, решения проблемы с использованием стиля передачи продолжения (CPS).
Предположим, у меня есть дерево, представляющее '(+ (* 5 6) (sqrt 3))
:
Индекс узлов начинается с 0 в корне и идет в ширину. На картинке выше я пометил все узлы их индексами, чтобы показать это.
Я хотел бы определить функцию subtree-bfs
, которая принимает дерево и номер индекса и возвращает поддерево с корнем по данному индексу. Например:
(define tree '(+ (* 5 6) (sqrt 3)))
(subtree-bfs tree 0) ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree-bfs tree 1) ; Returns: '(* 5 6)
(subtree-bfs tree 2) ; Returns: '(sqrt 3)
(subtree-bfs tree 3) ; Returns: 5
(subtree-bfs tree 4) ; Returns: 6
(subtree-bfs tree 5) ; Returns: 3
Я хотел бы решить проблему, используя стиль передачи продолжения. Как определить subtree-bfs
?
Пока что у меня это:
(define (node-children node)
;; (node-children 123) -> '()
;; (node-children (+ 1 (+ 2 3))) -> '(1 (+ 2 3))
(cond [(pair? node) (cdr node)]
[(null? node) (error "Invalid node" node)]
[else '()]))
(define (traverse-row& nodes index counter k)
;; 'counter' is the index number of the first node in 'nodes'.
(cond [(null? nodes) (k counter)]
[(= counter index) (car nodes)]
[else
(traverse-row& (cdr nodes)
index
(+ counter 1)
k)]))
(define (children-k children index k)
(if (null? children)
k
(lambda (counter)
(subtree-bfs& (car children)
index
counter
(children-k (cdr children) index k)))))
(define (subtree-bfs& nodes index counter k)
(traverse-row& nodes
index
counter
(children-k (map node-children nodes)
index
k)))
(define (subtree-bfs tree index)
(subtree-bfs& (list tree)
index
0
(lambda (max-index+1)
;; (- max-index+1 1) represents the maximum valid index number.
(error "Index out of bounds" index))))
Эта реализация работает правильно. Однако он кажется довольно длинным. Поскольку у меня нет опыта работы с CPS, я подумал, что должно быть лучшее решение CPS для этой проблемы. Есть ли лучшее решение CPS?
Примечание 1: Простите меня за неадекватное комментирование кода. Должен признаться, что я сам не до конца понимаю решение (!) Я скорее поражен тем, что мне вообще удалось найти решение.
Примечание 2. Этот вопрос может больше подходить для сайта проверки кода. Однако, учитывая отсутствие внимания к Scheme и Racket, на такой вопрос, скорее всего, никогда не будет ответа.