How do I replace part of a tree with another tree at the specified index?

Question

Suppose I have two trees:

• Tree A — '(+ (* 5 6) (sqrt 3)):

  

• Tree B — '(- 4 2):

  

Goal: replace one of tree A's subtrees with tree B at a specified tree A index position. The index position starts at 0 at the root node and is depth-first. In the figure for tree A above, I have labelled all the nodes with their index to show this.

For example, (replace-subtree treeA 4 treeB) replaces the subtree at index 4 in tree A with tree B, resulting in the tree (+ (* 5 6) (- 4 2)):

How do I implement (replace-subtree treeA index treeB)?

---

This question is somewhat related to my other question: How do I get a subtree by index?. I had great difficulty in solving it, but I eventually found a workable solution for that problem by using continuation-passing style (CPS). However, this problem here appears to be far more difficult. I am completely at loss as to how I should even begin! Implementations and clues are most welcome. I'd be particularly interested in implementations that do not use call/cc.

---

EDIT

I came up with a stopgap implementation while waiting for answers. It relies on set!, which I do not prefer.

(define (replace-subtree tree index replacement)
  (define counter 0)
  (define replaced #f)  ; Whether or not something has been replaced.

  (define (out-of-bounds-error)
    (error "Index out of bounds" index))

  (define (traverse-tree tree)
    (cond [(null? tree)
           (error "Invalid tree: ()")]
          [(= counter index)
           (set! counter (+ counter 1))
           (set! replaced #t)
           replacement]
          [(pair? tree)
           (set! counter (+ counter 1))
           (cons (car tree)
                 (traverse-children (cdr tree)))]
          [else
           ;; Possible only during the initial call to traverse-tree.
           ;; e.g. (replace-subtree 'not-a-list 9999 '(+ 1 2)) -> error.
           (out-of-bounds-error)]))

  (define (traverse-children children)
    (cond [(null? children) '()]
          [(list? (car children))
           ;; `list?` instead of `pair?` to let `traverse-tree` handle
           ;; invalid tree ().
           ;; `let*` instead of `let` to guarantee traversal of
           ;; first child first. In Scheme, order of evaluation of 
           ;; `let` bindings is unspecified.
           (let* ((first-child (traverse-tree (car children)))
                  (rest-child (traverse-children (cdr children))))
             (cons first-child rest-child))]
          [(= counter index)
           (set! counter (+ counter 1))
           (set! replaced #t)
           (cons replacement
                 (traverse-children (cdr children)))]
          [else
            (set! counter (+ counter 1))
            (cons (car children)
                  (traverse-children (cdr children)))]))

  (let ([result (traverse-tree tree)])
   (if replaced
       result
       (out-of-bounds-error))))

Answer 1

This is a harder problem than I expected it to be. One reason that it's hard is that the things you are calling 'trees' are not actually trees: they're DAGs (directed acyclic graphs) because they can share subtrees. Simple-mindedly this only happens for leaf nodes: in (a b b) the nodes with index 1 and 2 are eq?: they're the same object. But in fact it can happen for any node: given

(define not-a-tree
  (let ([subtree '(x y)])
    (list 'root subtree subtree)))

The nodes with index 1 and 2 are the same object and are not leaf nodes: this is a DAG, not a tree.

This matters because it derails an obvious approach:

1. find the node with the index you're interested in;
2. walk over the tree constructing new tree until you find this node, using eq? on nodes, and then replace it.

You can see that this would fail if I wanted to replace the node with index 2 in (x y y): it would replace the node with index 1 instead.

One approach which is probably then the simplest one is to take these 'trees' and turn them into trees where nodes do have identity. Then do the replacement on those trees as above, and then convert them back to the original representation. This will however possibly lose some structure which matters: the object above will be turned from a DAG to a tree, for instance. That's unlikely to matter in practice.

So to do this you'd need a function to take the old trees, turn them into new trees with suitable uniqueness, then convert them back. This is almost certainly the conceptually simplest approach but I was too lazy to write all that code.

So, here's an answer which is not that approach. Instead what this does is to walk over the tree keeping track of the node index as it goes, and building new tree if it needs to. To do this the thing that walks into a node needs to return two things: a node (which may be a newly-made node, i.e. the replacement, or the original node it was passed), and the new value of the index. This is done by returning two values from the walker, and there's a fair amount of hair around doing that.

This also doesn't try and use some little subset of Racket: it uses multiple values, including syntax (let-values) which makes them less painful to use, and also for/fold to do most of the work, including folding multiple values. So, you'll need to understand those things to see what it does. (It also probably means it's not suitable for a homework answer.)

One thing worth noting is that the walker cheats a bit: once it's done the replacement then it doesn't even try to compute the index properly: it just knows it's bigger than it cares about and cops out.

First here are abstractions for dealing with trees: note that make-node is not quite the same as the make-node in the answer to the previous question: it wants a list of children now which is a much more useful signature.

(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
  (cond
    [(cons? node)
     (car node)]
    [else
     node]))

(define (node-children node)
  ;; the children of a node as a list.
  (cond
    [(cons? node)
     (cdr node)]
    [else
     '()]))

Now here is the function that does the work.

(define (replace-indexed-subtree tree index replacement)
  ;; Replace the subtree of tree with index by replacement.
  ;; If index is greater than the largest index in the tree
  ;; no replacemwnt will happen but this is not an error.
  (define (walk/indexed node idx)
    ;; Walk a node with idx.
    ;; if idx is less than or equal to index it is the index
    ;; of the node.  If it is greater than index then we're not
    ;; keeping count any more (as were no longer walking into the node).
    ;; Return two values: a node and a new index.
    (cond
      [(< idx index)
       ;; I still haven't found what I'm looking for (sorry)
       ;; so walk into the node keeping track of the index.
       ;; This is just a bit fiddly.
       (for/fold ([children '()]
                  [i (+ idx 1)]
                  #:result (values (if (< i index)
                                       node
                                       (make-node (node-value node)
                                                  (reverse children)))
                                   i))
                 ([child (in-list (node-children node))])
         (let-values ([(c j) (walk/indexed child i)])
           (values (cons c children) j)))]
      [(= idx index)
       ;; I have found what I'm looking for: return the replacement
       ;; node and a number greater than index
       (values replacement (+ idx 1))]
      [else
       ;; idx is greater than index: nothing to do
       (values node idx)]))
  ;; Just return the new tree (this is (nth-value 0 ...)).
  (let-values ([(new-tree next-index)
                (walk/indexed tree 0)])
    new-tree))

So now

> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 4 '(- 4 2))
'(+ (* 5 6) (- 4 2))
> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 0 '(- 4 2))
'(- 4 2)
> (replace-indexed-subtree '(+ (* 5 6) (sqrt 3)) 20 '(- 4 2))
'(+ (* 5 6) (sqrt 3))

It's well worth putting a suitable printf at the top of walk/indexed so you can see what it's doing as it walks the tree.