質問は簡単です。Zipperのデータ構造を理解できません。
私の質問は、ツリーでの使用に関連しています。
ジッパーを使用してツリー ノードを変更する方法を知りたいです。そして、ツリー全体 (またはその大部分) をコピーしない方法。
ジッパーが間違っているかどうかを明確にしてください。多分それはツリーの更新に役立たないでしょうか？
または、ツリーを更新することは可能ですが、方法がわかりませんか?
10344 次
5 に答える
58
リストの 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))。
ジッパーは木と同じ考え方です。ツリー内の特定のフォーカスに加えて、コンテキスト (親まで、子まで) を表現します。これにより、ツリー全体がフォーカスで簡単に変更でき、フォーカスを上下に簡単に移動できる形になります。
于 2008-12-19T09:28:36.793 に答える
16
これは、Haskell のタイリング ウィンドウ マネージャーにジッパーを使用する方法を説明する非常に優れた記事です。ウィキペディアの記事はあまり参考になりません。
簡単に言えば、ジッパーは、ツリーまたはリスト構造内の特定のノードへのポインターまたはハンドルです。ジッパーは、ツリー構造を取得し、ツリーがフォーカスされたノードによって「ピックアップ」されたかのように扱う自然な方法を提供します。つまり、元のツリーの追加のコピーを作成したり、他のユーザーに影響を与えたりすることなく、2 番目のツリーを取得できます。木。
与えられた例は、最初にウィンドウを画面上の位置でソートし、次にフォーカスをモデル化するために、フォーカス ウィンドウに向けられたジッパーを使用する方法を示しています。フォーカス ウィンドウの特別なケースや追加のコードを記述することなく、挿入や削除などの O(1) 操作の優れたセットを取得できます。
于 2008-12-19T09:29:08.743 に答える
9
Learn You a Haskell にもジッパーに関する素晴らしい章があります。
于 2013-08-09T22:01:29.533 に答える
4
この記事は Haskell に関連していますが、zipper についてもかなり詳しく説明しており、Haskell 固有のものから簡単に抽象化できるはずです。
于 2008-12-20T15:34:21.183 に答える