2

This question is a follow-up on How do I get a subtree by index?. That question deals with depth-first indexing (for which I have provided a depth-first continuation-passing style solution). This question here is about breadth-first indexing, and specifically about solving the problem using continuation-passing style (CPS).

Suppose I have a tree that represents '(+ (* 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"];
}
dot -Tpng tree.dot -O

The index of nodes starts from 0 at the root, and is breadth-first. In the picture above, I have labelled all the nodes with their index to show this.

I would like to define a function subtree-bfs that takes a tree and an index number, and returns the subtree rooted at the given index. For example:

(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

I would like to solve the problem using continuation-passing style. How do I define subtree-bfs?


So far, I have this:

(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))))

This implementation appears to work correctly. However, it seems rather long. Since I am inexperienced with CPS, I thought that there must be a better CPS solution to this problem. Is there a better CPS solution?

Note 1: Forgive me for not adequately commenting the code. I must admit that I do not completely understand the solution myself (!) I am rather amazed that I was able to find a solution in the first place.

Note 2: This question may be more suitable for the code review site. However, given the lack of attention to Scheme and Racket over there, a question like this would likely never be answered.

Flux
  • 9,805
  • 5
  • 46
  • 92
  • Just to be clear: you know this is easy with an agenda-based search like the one I gave in the previous question? Obviously must be possible with CPS and it's fine to ask for a CPS answer obviously, but I find CPS too hard to get my head around. –  Dec 29 '20 at 16:37
  • 1
    @tfb Yes, thank you for that answer; it is what I would use in practice. Since I have already found a satisfactory CPS solution for depth-first, I thought that it might be instructive to find a CPS solution for breadth-first. It turns out that breadth-first is far more tricky than expected. – Flux Dec 29 '20 at 18:06
  • 1
    @tfb if that is the case may I humbly submit [this answer of mine](https://stackoverflow.com/questions/50554603/fill-a-nested-structure-with-values-from-a-linear-supply-stream/50588667#50588667) to your attention. I think it is clear and hope it can be illuminating. CPS linearizes computations and makes them essentially like recursive descent parsing. – Will Ness Dec 29 '20 at 18:06
  • 1
    @WillNess: thanks, I will read that. CPS is one of those things which I find I get what the idea is, and if I look at real code I can understand it, after a bit, while I'm looking at it but then 20 minutes later I have to understand it all over again. –  Dec 30 '20 at 10:03
  • 1
    @tfb someone once said, there's no real understanding (*"in math"* I think it was), one just becomes accustomed to things. :) writing CPS is like recursion, one needs to let go and just rely on the idea that if we do it right, then it should work. maybe something like that. :) – Will Ness Dec 30 '20 at 13:09
  • @WillNess: I think that's true in many ways: you don't understand something, but you force yourself to do it, and then sometime later, somehow, you do understand it. Or, perhaps you don't, but you are comfortable with it, as you say. –  Dec 30 '20 at 14:41

0 Answers0