Получить поддерево по индексу в ширину, используя стиль передачи продолжения

Этот вопрос является продолжением Как мне получить поддерево по индексу ?. Этот вопрос касается индексации в глубину (для которой я предоставил решение в стиле передачи продолжения в глубину). Этот вопрос здесь касается индексации в ширину и, в частности, решения проблемы с использованием стиля передачи продолжения (CPS).

Предположим, у меня есть дерево, представляющее '(+ (* 5 6) (sqrt 3)):

 GraphViz: digraph mytree { forcelabels=true; node [shape=circle]; +-›; +-›sqrt; node [shape=rect]; -›5; -›6; sqrt-›3; + [xlabel  =0]; [xlabel=1]; sqrt [xlabel=2]; 5 [xlabel=3]; 6 [xlabel=4]; 3 [xlabel=5]; } точка -Tpng tree.dot -O

Индекс узлов начинается с 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, на такой вопрос, скорее всего, никогда не будет ответа.


person Flux    schedule 29.12.2020    source источник
comment
Просто для ясности: вы знаете, что это легко с поиском на основе повестки дня, подобным тому, который я дал в предыдущем вопросе? Очевидно, что это возможно с CPS, и, очевидно, можно запросить ответ CPS, но я нахожу CPS слишком сложным, чтобы разобраться.   -  person    schedule 29.12.2020
comment
@tfb Да, спасибо за этот ответ; это то, что я бы использовал на практике. Поскольку я уже нашел удовлетворительное решение CPS для подхода в глубину, я подумал, что было бы полезно найти решение CPS для подхода в ширину. Оказывается, поиск в ширину гораздо сложнее, чем ожидалось.   -  person Flux    schedule 29.12.2020
comment
@tfb, если это так, могу ли я смиренно представить этот мой ответ вашему вниманию. Я думаю, что это ясно, и надеюсь, что это может пролить свет. CPS линеаризует вычисления и делает их по существу похожими на парсинг с рекурсивным спуском.   -  person Will Ness    schedule 29.12.2020
comment
@WillNess: спасибо, я прочитаю это. CPS — это одна из тех вещей, которые, как мне кажется, я понимаю, в чем заключается идея, и если я смотрю на настоящий код, я могу понять его, через некоторое время, пока я смотрю на него, но затем, через 20 минут, я должен понять все это. снова.   -  person    schedule 30.12.2020
comment
@tfb кто-то однажды сказал, что нет настоящего понимания (в математике я думаю, что было), человек просто привыкает к вещам. :) Написание CPS похоже на рекурсию, нужно отпустить ситуацию и просто положиться на мысль, что если мы все сделаем правильно, то это должно сработать. может что-то в этом роде. :)   -  person Will Ness    schedule 30.12.2020
comment
@WillNess: Я думаю, что во многих отношениях это так: ты чего-то не понимаешь, но заставляешь себя это делать, а потом через какое-то время каким-то образом понимаешь. Или, возможно, нет, но вас это устраивает, как вы говорите.   -  person    schedule 30.12.2020