問題タブ [zipper]

これは私の前の質問へのフォローアップです。イテレータ、、、などを使用してfold、zipScalaforeachのリストを反復処理できます。Zipperが最も適切なユースケースがあるのではないかと思います。同時実行のない読み取り専用アクセスが必要だとします。

そのような例を挙げて、なぜそれZipperが最良の選択なのか説明していただけますか?

これは、私の前の質問に対する回答のフォローアップです。

の各項目を関数でマップし、生成する必要がa:AあるとList[A]します。b:Bdef f(a:A, leftNeighbors:List[A]): BList[B]

明らかにmap、リストを呼び出すことはできませんが、リストジッパーを使用することはできます。ジッパーは、リスト内を移動するためのカーソルです。現在の要素 ( focus) とその隣接要素へのアクセスを提供します。

fこれで、 myを に置き換えて、def f'(z:Zipper[A]):B = f(z.focus, z.left)この新しい関数f'をcobindメソッド ofに渡すことができZipper[A]ます。

動作は次のcobindようになります: ジッパーでそれを呼び出し、次にジッパーを移動し、新しいf'「移動した」ジッパーで呼び出し、再びジッパーを移動する、というように... ジッパーがリストの最後に到達するまで。 f'

最後に、cobindはタイプ の新しいジッパーを返しますZipper[B]。これはリストに変換できるため、問題は解決されます。

ここで、cobind[A](f:Zipper[A] => B):Zipper[B]との間のbind[A](f:A => List[B]):List[B]対称性に注意してください。ListMonadZipperComonad

それは理にかなっていますか？

現在、XML 変換を扱っています。例えば、

• すべてのノード<a>を<b>
• <c x = "xxx">すべてのノードを<d y="xxx">etcに置き換えます。

標準scala.xml の RewriteRuleとRuleTransformer. それを拡張RewriteRuleしてインスタンスに渡しRuleTransformerます。これにより、ルールが XML に適用されます。

lenses、 など、その仕事のための他のツールがあることは知っていzippersます。それらは、必要に応じて XML を変換できますか? 私の現在のアプローチと比較して、それらの利点は何ですか?

このプレゼンテーション[2005] では、スライド 32 を読みました。

ジッパー データ型はコモナドを隠します。これはまさに、属性評価を構築するために必要なコモンドです。

したがって、 Zippers を Comonads で表現できるようです。これは Scala でも可能なようです。

ジッパー ソースを見ると、Clojure メタデータとして表現されているジッパーが表示されます。

私の質問は、Clojure Zippers が comonads として表現されることで利益を得るという証拠は何ですか?

エリックは、メリットは

そのため、元のグループに可能なすべてのジッパーを取得する必要があります!

バイナリ ツリー ジッパーを comonad のインスタンスにしたいのですが、duplicate適切に実装する方法がわかりません。

これが私の試みです：

いくつかの説明：

• BinTree aはバイナリ ツリー データ型で、各ツリー ノードにはラベルが含まれます。
• Partial a左または右の部分木を持つ二分木です。私のコードのスタックはPartial a 、データ コンテキストの役割を果たします。
• BTZBinTreeのインスタンスを作成したいジッパーを表しComonad、データ コンテキストとフォーカス サブツリーで構成されます。

のインスタンスにするためにComonad、私の計画は と を実装extractしduplicate、いくつかのランダムなバイナリ ツリーを取得して、コモナド プロパティが保持されるかどうかを検証することです。

これextractは簡単で、フォーカス サブツリーを取り出すだけです。

関数dupは、各ノード ラベルをそのノードに焦点を当てたツリー ジッパーに置き換える補助関数として機能します。

の場合duplicate z、ノード ラベルはzそれ自体である必要がありextract . duplicate == idます。非リーフ ノードのdup場合、親がいないかのようにサブツリーを処理し、現在のフォーカスzと残りのデータ コンテキストが後でこれらのジッパーに追加されます。

これまでのところ、最初の 2 つの comonad プロパティ (extract . duplicate = idおよびfmap extract . duplicate) は満たされていますが、データ コンテキストをどうするかはわかりません。私が現在していることは、ジッパーを取り、z上げ続けることです. 途中で、各データ コンテキスト スタックのトップを取得して新しいデータ コンテキスト スタックを構築します。これは正しいように聞こえますが、正しい型 ([Partial (BTZ a)]です。しかし、私のアプローチでは第 3 法則を満たすことはできません。

上記のバイナリ ツリー ジッパーのデータ型定義を考えると、それを Comonad のインスタンスにすることは可能ですか? 答えが「はい」の場合、私のアプローチに何か問題がありますか?

たとえば、特定のリストまたは配列に対して

たとえば、コレクション型との間でマッピングされる特定の関数

orfの i 番目の要素に適用する方法listarray

そしてまた

私は clojure の初心者で、clojure.zip を使用していましたが、その中で編集機能を使用する方法を理解できませんでした。誰かがそれがどのように機能するかの実例を私に与えることができれば、それは本当に役に立ちます.

たとえば、二分木があるとします

値 57 を編集して 75 に変更するにはどうすればよいですか

決定論的有限オートマトンをデータ構造として使用する単純な辞書圧縮アルゴリズムを実装しようとしています (実際には決定論的非巡回有限状態オートマトンです。ウィキペディアのエントリを参照してください)。大規模なレキシコン データベースに対してプログラムを実行すると (2 つのデータセットがあります。1 つには ~900.000 個の一意の単語が含まれ、もう 1 つには ~4.000.000 個の一意の単語が含まれています)、ヒープ オーバーフローが発生します。

私の推測では、問題の 1 つはaddWordおよびaddWords関数の遅延です。

seq、$!およびについて読み!ましたが、例でそれらをどのように使用できるかまだわかりません。コードを厳密にするにはどうすればよいですか? 一方、間違ったデータ構造 (ツリー + ジッパー) を使用している可能性がありますか?

これは、（それほどではありませんが）短く、自己完結型で、正しい（コンパイル可能）、私がやっていることの例です。実行すると、状態の数、遷移の数、および DFA ツリー全体が次のように出力されます。

コード：