問題タブ [zipper]

質問は簡単です。Zipperのデータ構造を理解できません。

私の質問は、ツリーでの使用に関連しています。

ジッパーを使用してツリー ノードを変更する方法を知りたいです。そして、ツリー全体 (またはその大部分) をコピーしない方法。

ジッパーが間違っているかどうかを明確にしてください。多分それはツリーの更新に役立たないでしょうか？
または、ツリーを更新することは可能ですが、方法がわかりませんか?

だから私はHaskell（そして他の関数型言語だと思います）のZipperパターンについて少し読んで、データ構造をトラバースして変更しました。これは私が型を作成するスキルを磨く良い機会になると思いましたHaskellのクラス。このクラスは、トラバースされるデータ構造に関係なく、コードを書き込むための共通のトラバーサルインターフェイスを提供できるためです。

おそらく2つのクラスが必要だと思いました。1つはルートデータ構造用で、もう1つは最初のクラスをトラバースするために作成された特別なデータ構造用です。

しかし、リストのようないくつかの単純なデータ構造でこれらを試したとき：

または二分木：

コンパイルできませんでした。Zippableインスタンス定義ごとに、次のようなエラーがたくさん発生します。

だからここからどこへ行けばいいのかわからない。私の問題は、(Zipper z) =>宣言zがいずれかである必要があるときに、これら2つのインスタンスをバインドしようとしていることだと思いますZipper。

次のようなXMLがあるとします。

ここで、zip_filter / xml.cljのサンプルを調べて、関心のある単一の値を取得する方法を見つけました。

（ce）のテキスト値のペアのリストを返すようなことをどのように行うのか疑問に思っています。

編集：

ここにいくつかの動作するコードがありますが、それはかなり醜いです。些細なリファクタリングを求めていませんが、ジッパーがこれを行うためのより良い方法はありますか？

ジッパーは素晴らしいアイデアだと思います。リストまたはツリーをたどって、機能的な方法でローカル更新のように見えるものを作成する方法をエレガントに提供します。

漸近的に、コストは合理的であるように見えます。ただし、データ構造をトラバースするには、反復ごとにメモリを割り当てる必要があり、通常のリストまたはツリーのトラバーサルは単なるポインター追跡です。これは高価に思えます (間違っていたら訂正してください)。

コストは法外ですか？また、どのような状況でジッパーを使用するのが合理的でしょうか?

orange node次のツリーでを変更したいとします。

したがって、他に必要な変更は の だけleft pointerですgreen node。

はblue nodeそのままです。

私はどこか間違っていますか？この記事(ジッパーについて説明しています) によると、青色のノードも変更する必要があるためです。

同様に、同じ記事のこの図 (色を変更)では、(ノードを変更したときに) オレンジ色のノードをまったく変更するのはなぜxですか?

ネストされたベクトルとして表されるツリーがあります。indexedこのように各ノードのインデックスを表示して、ツリーの一般化を行いたいです。

ナイーブな実装はclojure.zipを直接使用します（すでにここで尋ねられているように）

ただし、を繰り返すとclojure.zip/next、事前順序トラバーサルが実行され、この場合は無限ループになります（未訪問のノードは無限conjに[:found]ベクトルになります）。別のアプローチはを使用することclojure.walk/postwalkですが、インデックスなどの構造情報を提供しません。

これをどのように実装しますか？postorder-nextすぐに解決するforzipはありますか？

Zipper データ構造は、ツリーをトラバースして現在の位置を維持したい場合に最適ですが、複数の位置を追跡したい場合はどのデータ構造を使用すればよいでしょうか?

例を挙げて説明しましょう：

• #haskell チャンネルの誰かが、yi エディターではカーソル位置を表すためにジッパーが使用されていると教えてくれました。これはすばらしいことですが、カーソルを 2 つにしたい場合はどうすればよいでしょうか。選択を表現したい場合と同様に、選択の開始と終了を知る必要があります。
• ウィキブックの Minotaur の例では、Zipper を使用して、迷宮内の Minotaur の位置を表しています。迷宮に敵を追加したい場合は、ジッパーで敵の位置を表すのが理にかなっています。
• 最後の 1 つは、すべてが始まった私のミニ プロジェクトからのものです。Haskell の学習の一環として、cairo と gth2hs を使用してツリー構造を視覚化しようとしています。ここまではうまくいきましたが、今度は 1 つまたは複数のノードを選択して、たとえば移動できるようにしたいと考えています。選択したノードが複数ある可能性があるため、教科書で定義されているように Zipper をそのまま使用することはできません。

hereで説明されているように、有限マップを含む XMonad の初期バージョンで使用されていたものと同様の、簡単な (単純な?) ソリューションがあります。

つまり、たとえば私のサンプル プロジェクトの場合、選択したノードをインデックス付きマップに格納し、メイン構造内のそれらの表現をインデックスに置き換えます。しかし、このソリューションには多くの欠点があります。上記のリンクで説明されているように、または私の例の場合、すべてのノードの選択を解除するには、ツリー全体を検索する必要があります。

次の2つのcase classesがあるとします。

および次のPersonクラスのインスタンス：

を更新したい場合zipCodeは、次のrajことを行う必要があります。

ネストのレベルが高くなると、これはさらに醜くなります。update-inそのようなネストされた構造を更新するためのよりクリーンな方法（Clojureのようなもの）はありますか？

遺伝的プログラミングの問題のために s 式のツリーを作成していますが、進化の過程でツリーの一部を変更する必要があります。完璧なClojureのジッパー機能に出会いましたが、私の人生では使い方がわかりません。

たとえば、ジッパーを作成するとします

これは、ルートに + があるツリーを表していると理解しています。次のようなものです。

ただし、私のジッパーはこれに同意しません。最初のノードを要求すると、(-> zipped zip/down zip/node)(+正しい) が返されますが、 に(-> zipped zip/down zip/down)移動せず-、代わりに が返されますnil。確かに(-> zipped zip/down zip/rights)、ツリーの残りの部分をルートの右側に兄弟として与えます。これは、ツリーがまったくないことを示唆しています。

ツリーを実行すると正しい答えが得られるため、ツリーを正しく表現していると確信しています。ジッパーは別のレイアウトを期待していますか?

独自のマップからジッパーを作成しようとしています。ジッパーの定義によると、

パラメータブランチ？そして子供たちは明確であり、私はそれを定義することができます. しかし、make-node 関数はややこしいです。使用されているとは思わない実装を行いました。

の地図を持っています

この地図からジッパーを作りたいです。だから私は次のジッパー関数呼び出しを使用しました、

これはうまくいきます。make-node パラメーターに nil を指定しても機能します。このパラメーターがいつどこで使用されるのかわかりません。