ツリーの一部を指定されたインデックスの別のツリーに置き換えるにはどうすればよいですか？
2本の木があるとします。
ツリーA—
'(+ (* 5 6) (sqrt 3))：
ツリーB—
'(- 4 2)：
目標：指定されたツリーAのインデックス位置で、ツリーAのサブツリーの1つをツリーBに置き換えます。インデックス位置はルートノードで0から始まり、深さ優先です。上記のツリーAの図では、これを示すためにすべてのノードにインデックスを付けています。
たとえば(replace-subtree treeA 4 treeB)、ツリーAのインデックス4のサブツリーをツリーBに置き換えると、ツリーは(+ (* 5 6) (- 4 2))次のようになります。
どうすれば実装でき(replace-subtree treeA index treeB)ますか？
この質問は、他の質問と多少関連しています。インデックスでサブツリーを取得するにはどうすればよいですか。。私はそれを解決するのに非常に苦労しましたが、最終的には継続渡しスタイル（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))))
回答
これは私が思っていたよりも難しい問題です。難しい理由の1つは、「ツリー」と呼んでいるものが実際にはツリーではないことです。サブツリーを共有できるため、DAG（有向非巡回グラフ）です。簡単に言えば、これはリーフノードでのみ発生します。(a b b)インデックス1と2のノードeq?には、同じオブジェクトがあります。しかし実際には、どのノードでも発生する可能性があります。
(define not-a-tree
(let ([subtree '(x y)])
(list 'root subtree subtree)))
インデックス1と2のノードは同じオブジェクトであり、リーフノードではありません。これはDAGであり、ツリーではありません。
これは明らかなアプローチを狂わせるので重要です：
- 興味のあるインデックスを持つノードを見つけます。
eq?onノードを使用して、このノードが見つかるまで新しいツリーを構築するツリーの上を歩き、それを置き換えます。
でノードをインデックス2に置き換えたい場合、これは失敗することがわかり(x y y)ます。代わりに、ノードをインデックス1に置き換えます。
おそらく最も簡単なアプローチの1つは、これらの「ツリー」を取得して、ノードがIDを持つツリーに変換することです。次に、上記のようにそれらの木を置き換えてから、元の表現に変換し直します。ただし、これにより、重要な構造が失われる可能性があります。たとえば、上記のオブジェクトはDAGからツリーに変換されます。それが実際に問題になる可能性は低いです。
したがって、これを行うには、古い木を取得し、適切な一意性を持つ新しい木に変換してから、元に戻す関数が必要になります。これはほぼ間違いなく概念的に最も単純なアプローチですが、私は怠惰すぎてそのすべてのコードを書くことができませんでした。
だから、ここにそのアプローチではない答えがあります。代わりに、これが行うことは、ノードインデックスを追跡しながらツリー上を歩き、必要に応じて新しいツリーを構築することです。これを行うには、ノードに入るものが2つのものを返す必要があります。ノード（新しく作成されたノード、つまり置換、または渡された元のノード）とインデックスの新しい値です。これは、ウォーカーから2つの値を返すことによって行われます。これを行うには、かなりの量の髪の毛があります。
これはまた、Racketの小さなサブセットを使用しようとはしません。構文（let-values）を含む複数の値を使用するため、使用for/foldの手間が軽減され、複数の値を折りたたむなど、ほとんどの作業が実行されます。したがって、それが何をするのかを知るには、それらを理解する必要があります。（それはおそらく宿題の答えには適していないことを意味します。）
注目に値することの1つは、ウォーカーが少しごまかしていることです。置換が完了すると、インデックスを適切に計算しようとさえしません。気にかけているよりも大きいことを認識し、対処します。
まず、ツリーを処理するための抽象化を示します。前の質問への回答make-nodeとはまったく同じではないことに注意してくださいmake-node。これは、はるかに便利な署名である子のリストが必要です。
(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があります。