tree - 如何用指定索引处的另一棵树替换树的一部分？

Question

假设我有两棵树:

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

树 B — '(- 4 2) :

目标:在指定的树 A 索引位置用树 B 替换树 A 的子树之一。索引位置从根节点的 0 开始，并且是深度优先的。在上面树 A 的图中，我用它们的索引标记了所有节点以显示这一点。
例如， (replace-subtree treeA 4 treeB)用树 B 替换树 A 中索引 4 处的子树，得到树 (+ (* 5 6) (- 4 2)) :

我如何实现 (replace-subtree treeA index treeB) ?

这个问题与我的另一个问题有些相关: How do I get a subtree by index? .我在解决它时遇到了很大的困难，但我最终通过使用连续传递样式 (CPS) 找到了解决该问题的可行解决方案。然而，这里的这个问题似乎要困难得多。我完全不知道我应该如何开始!实现和线索是最受欢迎的。我对不使用 call/cc 的实现特别感兴趣。 .

编辑
在等待答案时，我想出了一个权宜之计。它依赖于 set! ，我不喜欢。

(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 ().
           (cons (traverse-tree (car children))
                 (traverse-children (cdr children)))]
          [(= 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

这是一个比我预期的更难的问题。很难的一个原因是你称之为“树”的东西实际上并不是树:它们是 DAG(有向无环图)，因为它们可以共享子树。简单地说，这只发生在叶节点上:在 (a b b) 中索引为 1 和 2 的节点是 eq? : 他们是同一个对象。但实际上它可能发生在任何节点上:给定

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

索引为 1 和 2 的节点是同一个对象，不是叶节点:这是一个 DAG，而不是一棵树。
这很重要，因为它破坏了一个明显的方法:

找到具有您感兴趣的索引的节点；

使用 eq? 遍历构建新树的树，直到找到该节点。在节点上，然后替换它。

您可以看到，如果我想用 (x y y) 中的索引 2 替换节点，这将失败。 :它会用索引 1 替换节点。
一种可能是最简单的方法是采用这些“树”并将它们变成节点确实具有标识的树。然后像上面那样对这些树进行替换，然后将它们转换回原始表示。然而，这可能会丢失一些重要的结构:例如，上面的对象将从 DAG 变成树。这在实践中不太可能。
所以要做到这一点，你需要一个函数来获取旧树，将它们变成具有合适唯一性的新树，然后将它们转换回来。这几乎可以肯定是概念上最简单的方法，但我懒得写所有的代码。
所以，这是一个不是这种方法的答案。相反，它的作用是遍历树以跟踪节点索引，并在需要时构建新树。为此，进入节点的事物需要返回两件事:一个节点(可能是新创建的节点，即替换节点，或者它被传递的原始节点)，以及索引的新值。这是通过从 walker 返回两个值来完成的，并且在这样做时有相当多的头发。
这也不会尝试使用 Racket 的一些小子集:它使用多个值，包括语法( let-values )，这使它们使用起来不那么痛苦，还有 for/fold完成大部分工作，包括折叠多个值。因此，您需要了解这些内容才能了解它的作用。 (这也可能意味着它不适合家庭作业答案。)
值得注意的一件事是，walker 有点作弊:一旦完成替换，它甚至不会尝试正确计算索引:它只是知道它比它关心的要大，然后警察出去了。
首先是处理树的抽象:注意 make-node与 make-node 不太一样在上一个问题的答案中:它现在想要一个 child 的列表，这是一个更有用的签名。

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

现在这是完成工作的功能。

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

所以现在

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

很值得放一个合适的 printf顶部 walk/indexed这样你就可以看到它在树上行走时在做什么。