すばらしいジッパー、または心配しないことを学び、ツリーデータ構造を愛した方法

ツリーはかなり複雑な構造であることが知られています。 そして、再帰（問題がないわけではない）を含め、読み取りが正常に実装されている場合、変更によって事態はまったく改善されません。



同時に、長い間、木を扱うための非常に効果的なツールがあります-ジッパーですが、広く配布されていないので、私はその理由を知っています。



ジッパーの古典的な概念的な説明は、次のようになります。 逆さのグローブのように、裏返しになっているようなツリー構造の内部の外観です。



この比fig的な説明は、脳がきしむ場合、通常、部分的にしか理解されていません。 次に、 「これは、モナドなどの不可解な機能上の問題であるため、それを把握します。 」



著者「後」はすでに来ています。 この記事は、実際のタスクでジッパーをすばやく理解してすぐに使い始めることができるように、ジッパーの代替説明を提供する試みです（代替ギフトの説明と混同しないでください...）。



アイデアがどのように発展したか考えてみましょう。



データのシーケンスがあると仮定します。 ベクトル（配列）とします。











これは、作業が必要なシンボル要素を持つベクトルです。 左右に歩いてキャラクターを読む必要があります。 当然のことながら、1つの要素の幅を持つ特定の「ウィンドウ」というアイデアが生まれ、それを左右にシフトできます。











実際、ベクトルを操作するための特定のコンポーネントカーソルを取得しました。これは、左右に移動して現在の位置からデータを読み取ることができます。 アイデアの自然な発展は、このコンポーネントを追加機能で強化することです。 彼に、現在をシフトさせて読むことに加えて、私たちがどこにいるのかを教えてください：











さらに進んで、このコンポーネント用のそのようなAPIを作成できます。

• ステップ左
• ステップ右
• 現在の値
• 左に配置
• 右に配置
• 一番左 ？
• 極右 ？
• 現在の値を置き換える
• 値を左に貼り付け
• PasteValueRight
• DeleteCurrentValue

カーソルコンポーネントは、ベクトルやシンボルに結び付けられていないことに注意してください。つまり、任意のタイプの要素を持つコレクションに使用できます。 非常に優れたコンポーネント。



木はどうですか？ 木に似たものを考え出してみませんか？ 簡単！











ツリーの場合、新しい可能性が自然に追加されました。今では、左右だけでなく上下にも歩くことができ、ツリーのルートにいるかリーフにいるかを判断できます。

そして、もちろん、APIを充実させるために、すぐにかゆみを起こしてください。

• ステップ左
• ステップ右
• ステップアップ
• ステップダウン
• 現在の値
• ルート値
• 子の値
• 左に配置
• 右に配置
• ポジショントップ
• 一番左 ？
• 極右 ？
• 根
• シート ？
• 現在の値を置き換える
• 値を左に貼り付け
• PasteValueRight
• DeleteCurrentValue

ご列席の皆様、私に紹介しましょう... ジッパー ！



明らかに、上記のAPIは完全ではありません。当然、深さ優先検索の2つのメソッドを追加する必要があります。PreviousおよびNextで、検索ルールに従ってウィンドウを前後に移動します。 便宜上、AddDesignValueメソッドを追加できます。 一般的に、実装の詳細にスムーズに移行していますが、これは実行しませんでした。



主なことは、私たちがアイデア自体を見つけたということです。それは今では非常に平凡で自然に思えます。



そして、悪名高い手袋はどこで裏返しになっていますか？



はい、ここに彼女がいます！ メソッドPosition Left 、 Position Right 、 Position Above を Values Left 、 Values Right 、 Values Aboveに置き換えると、「内部からツリーを見る」ことができます。現在の値があり、

• 残りの値
• 値右
• 上記の値
• 子の値

逆さ手袋とは何ですか？



練習に行くことができます。



しかし、最初に、1つの省略を補います。 ジッパーは機能的な概念であり、つまり、永続的なデータ構造（大まかに言って、データは変更されず、新しいデータのみが作成されます）、第1クラスのオブジェクトとして機能する（大まかに言えば、パラメーターで渡すことができる）場合に最も効果的です。それだけです。



プラットフォームが効率的に実装された永続構造を提供する場合、ジッパーは効率的で低コストの（価値のない）コンポーネントとして自動的に取得されます。 オーバーヘッドをあまり心配することなく、必要に応じて安全に作成および再作成できます。



プラットフォーム-clojure（スクリプト）-永続的な構造を提供します。 それだけでなく、zip自体も提供します：clojure.zip名前空間、 ソースコードに精通することをお勧めします-シンプルでクリーンな実装。



2回目の省略を記入します。 ベクターのカーソルの場合、カーソルはベクターにも文字にも結び付けられておらず、どのコレクションでも使用できます。



ジッパーはどうですか？



すべてがまったく同じです！ 概念的には、ジッパーは構造にもデータにも添付されません。つまり、任意のツリーで使用できます。 言い換えれば、ジッパーを使用すると、ツリー処理アルゴリズムをその構造から抽象化できます。



たとえば、Clojure.zipは、ニーズに合わせてジッパーを作成するジッパー関数を提供します。



（ジッパーブランチ？子make-nodeルート）

• 支店 ？ -関数は、渡されたノードに応じて、原則としてブランチを決定します（子ノードを持つことができるかどうか）。
• children-渡されたブランチ上の関数は、子ノードのコレクションを返します。
• make-node-関数。渡されたノードと子のコレクションによって、ツリーブランチ、つまり送信された子を持つノードを返します。
• root-ルートノード、つまりツリー自体。

この関数を使用して、特定の構造で機能するジッパーを作成できます。 このような小さなツリーがあるとしましょう：

(def sample-tree {:tag :div :content [ {:tag :span :content ["  "]} {:tag :span :content ["!"]} ]})
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ジッパーを作成します。

 (require '[clojure.zip :as z]) ;    
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

 (def sample-z (z/zipper (fn [node] (not (string? node))) ;      (fn [node] (vec(:content node))) ;  :content       ( ,  nil ) (fn [node children] (assoc node :content (vec children))) ;   :content     sample-tree)) ;  
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ツリーの全文を取得するにはどうすればよいですか？

 (loop [z sample-z result ""] ;    z  result (if (z/end? z) ;      result ;   (recur (z/next z) (if (z/branch? z) result (str result (z/node z)))))) ;     
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

実行結果：“ おはようございます、国！ ”ツリーのトラバーサルは、再帰的ではなく反復的に行われることに注意してください。



呼び出しの後にコンマをスペースで挿入します。 すぐに言ってやった！

 (def new-z (-> sample-z z/next (z/insert-right {:tag :span :content [", "]})))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

new-zは修正されたジッパーです。 実際に変更されたツリーが必要な場合：

 (def new-tree (z/root new-z))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

基本的なAPIはlojure.zipスペースの関数の形式で実装されていますが、ジッパー自体を調べると便利な場合があります。そのためには、それが何であるかを理解する必要があります。 この実装では、これは単に2つのコンポーネントのベクトルです。現在のツリーノードと、キーでその位置（同じグローブ）を記述するマップです。

• ：l-左側のノード
• ：r-右側のノード
• ：pnodes-上記のノード（ルートへのパス）
• ：ppath-親グローブのコピー
• ：変更されましたか？ -このジッパーを介してツリーが変更されたことを示す記号

この例では、 new-zは次のようになります。

 [{:content ["  "], :tag :span} ;   {:changed? true, :l [], :pnodes [{:content [{:content ["  "], :tag :span} {:content ["!"], :tag :span}], :tag :div}], :ppath nil, :r ({:content [", "], :tag :span} {:content ["!"], :tag :span})}]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ところで、この記事のすべての例は、展開に煩わされることなく、問題なくオンラインREPLに移行できます。



そして、ちょっとした用語：ジッパーは概念であり、アイデアです。 特定のインスタンス（この例のnew-zなど）は通常、ロケーションと呼ばれ、非常に論理的です。



以上です。 この記事が、苦しんでいる機能的な木こりの苦労を助けてくれますように！ ご清聴ありがとうございました。



UPD： qnikstは、この記事には理論への言及がないことに非常に正確に気づきました。これは、「 特定の構造のためにジッパーを整理するにはどうすればよいか」という実用的な質問に答えるのに非常に役立ちます 構造のジッパーを数学的に正確に選択できると便利ではないでしょうか？！

これを行うには、データ構造を代数的に記述し、結果の式を区別できる必要があります。 誰もが学校から2番目の方法を知っていますが、最初の方法は差し込むことができます。 それ自体では、この質問は私にとって非常に興味深いようであり、実際のプレゼンテーションはまだ利用可能ではない別の記事に基づいています。 したがって、このトピックで見つけた最高の資料に興味のある人をロシア語でインターネットに送ります。

データの代数と突然変異の計算（翻訳）



そして、「代数データ型」の概念のより完全でより学術的な説明のために、写真を完成させる別のリンク： ジャーナル「関数型プログラミングの実践」