質問は簡単です。ジッパーデータ構造。
私の質問は、ツリーでの使用に関するものです。
ジッパーを使用してツリー ノードを変更する方法を理解したいです。また、ツリー全体 (またはその大部分) をコピーしない方法も知りたいです。
ジッパーについて私が間違っているかどうかを明確にしてください。ツリーの更新には役立たないのでしょうか?
あるいは、ツリーを更新することは可能で、方法がわからないだけなのでしょうか?
ベストアンサー1
まず、リストの Zipper 類似物から始めましょう。リストの n 番目の要素を変更する場合、最初の n-1 要素をコピーする必要があるため、O(n) かかります。代わりに、リストを構造 ((最初の n-1 要素を反転) n 番目の要素 (残りの要素)) として保持できます。たとえば、(1 2 3 4 5 6)3 で変更可能なリストは と表されます((2 1) 3 (4 5 6))。これで、3 を別のものに簡単に変更できます。フォーカスを左右((1) 2 (3 4 5 6))に簡単に移動することもできます((3 2 1) 4 (5 6))。
ジッパーは、ツリーに適用された同じアイデアです。ツリー内の特定のフォーカスとコンテキスト (親まで、子まで) を表すことで、フォーカスで簡単に変更でき、フォーカスを上下に簡単に移動できる形式でツリー全体が得られます。