tree - How do I get a subtree by index?

Question

Suppose I have the following tree:

In my program, this tree is represented using a list: '(+ (* 5 6) (sqrt 3)).

How do I get a subtree by its index?

The index should start from 0 and be depth-first. In the picture above, I have labelled all the nodes with their index to show this.

For example:

(define tree '(+ (* 5 6) (sqrt 3)))

(subtree tree 0)  ; Returns: '(+ (* 5 6) (sqrt 3)))
(subtree tree 1)  ; Returns: '(* 5 6)
(subtree tree 2)  ; Returns: 5
(subtree tree 3)  ; Returns: 6
(subtree tree 4)  ; Returns: '(sqrt 3)
(subtree tree 5)  ; Returns: 3

I tried to implement subtree like this:

(define (subtree tree index)
  (cond [(= index 0) tree]
        [else
         (subtree (cdr tree)
                  (- index 1))]))

However, this does not traverse into sublists. It is incorrect.

EDIT:

I tried to implement subtree using continuation-passing style:

(define (subtree& exp index counter f)
  (cond [(= counter index) exp]
        [(null? exp) (f counter)]
        [(list? exp)
         (let ((children (cdr exp)))
           (subtree& (car children)
                     index
                     (+ counter 1)
                     (lambda (counter2)
                       (if (null? (cdr children))
                           (f counter)
                           (subtree& (cadr children)
                                     index
                                     (+ counter2 1)
                                     f)))))]
        [else (f counter)]))

(define (subtree tree index)
  (subtree& tree
            index
            0
            (lambda (_)
              (error "Index out of bounds" index))))

This works correctly for trees like:

• '(+ 1 2)
• '(+ (* 5 6) (sqrt 3))

However, it fails for trees like:

• '(+ 1 2 3)

What is wrong with my implementation?

Answer 1

The way to do this without hairy control constructs is with an agenda.

But before you do that, define abstractions. Every time I look at code which is walking something it calls a 'tree' and is full of explicit car, cdr &c I have to stop myself from simply cold-booting the universe in the hope we get a better one. If whoever is teaching you is not telling you this have strong words with them.

Here are some abstractions for the tree structure. These are particularly important because the tree structure is really irregular: I want to be able to say 'give me the children of this node' on any node: leaves are just nodes with no children, not some special kind of thing.

(define (make-node value . children)
  ;; make a tree node with value and children
  (if (null? children)
      value
      (cons value children)))

(define (node-value node)
  ;; the value of a node
  (if (cons? node)
      (car node)
      node))

(define (node-children node)
  ;; the children of a node as a list.
  (if (cons? node)
      (cdr node)
      '()))

Now some abstractions for the agenda. Agendas are represented as lists, but nothing else knows this of course, and a more industrial-strength implementation might well not want to represent them like that.

(define empty-agenda
  ;; an empty agenda
  '())

(define agenda-empty?
  ;; is an agenda empty?
  empty?)

(define (agenda-next agenda)
  ;; return the next element of an agenda if it is not empty
  ;; error if it is
  (if (not (null? agenda))
      (car agenda)
      (error 'agenda-next "empty agenda")))

(define (agenda-rest agenda)
  ;; Return an agenda without the next element, or error if the
  ;; agenda is empty
  (if (not (null? agenda))
      (cdr agenda)
      (error 'agenda-rest "empty agenda")))

(define (agenda-prepend agenda things)
  ;; Prepend things to agenda: the first element of things will be
  ;; the next element of the new agenda
  (append things agenda))

(define (agenda-append agenda things)
  ;; append things to agenda: the elements of things will be after
  ;; all elements of agenda in the new agenda
  (append agenda things))

Now it's easy to write a purely iterative version of the function (the agenda is maintaining the stack), without all sorts of hairy control constructs.

(define (node-indexed root index)
  ;; find the node with index index in root.
  (let ni-loop ([idx 0]
                [agenda (agenda-prepend empty-agenda (list root))])
    (cond [(agenda-empty? agenda)
           ;; we're out of agenda: raise an exception
           (error 'node-indexed "no node with index ~A" index)]
          [(= idx index)
           ;; we've found it: it's whatever is next on the agenda
           (agenda-next agenda)]
          [else
           ;; carry on after adding all the children of this node
           ;; to the agenda
           (ni-loop (+ idx 1)
                    (agenda-prepend (agenda-rest agenda)
                                    (node-children
                                     (agenda-next agenda))))])))

---

A thing to think about: what happens if you replace agenda-prepend by agenda-append in the above function?