Data.Sequenceでinitとtailはどのように機能しますか？

それは私です！

おそらく最善のアプローチは、例を通して作業することだと思います。行きましょう...

Deep (Two 1 2)                                                    (Two 7 8))
                (Deep (One (Node2 3 4))        (One (Node2 5 6))
                                         Empty

これがシーケンスです。多少簡略化されています（たとえば、Elemラッパーを省略しています）。

これについて初期化を行いましょう。尾は本質的に対称です。私たちの再帰的アルゴリズムは、空のinitを除外し、空でないものだけを含めます。

プレフィックス

したがって、initのプレフィックス桁は、基本的にfmap digitToTree (initsDigit (Two 1 2))。で生成されます。

initsDigit (Two 1 2) = Two (One 1) (Two 1 2)
fmap digitToTree (Two (One 1) (Two 1 2)) = 
    Two (Single 1) (Deep (One 1) Empty (One 2))

したがって、これらは全体の最初の2つの初期値であり、この数字はの結果の接頭辞の数字になりinitsます。（すべて完了した後に空のシーケンスを先頭に追加することを除いて、今はそれを無視しましょう。）

インナーツリー

ここで、内部ツリーの初期化を取りましょう。これはFingerTree (Node a)-として扱われます。ノードを引き離すつもりはありません。これは、2FingerTreeつのノードを含む2つの要素にすぎません。これについては詳しく説明しません。同じアルゴリズムを繰り返し実行するだけで、魔法のように結果に到達します。

Deep 
    (One (Single (Node2 3 4))) 
    Empty 
    (One (Deep (One (Node2 3 4)) Empty (One (Node2 5 6))))
  :: FingerTree (FingerTree (Node a))

つまり、これらは内側のツリーの初期段階です。これらは外側の木の初期化にどのように対応していますか？内側のツリーの各初期化は、を含むツリーに対応します

• 元のツリーのプレフィックス桁、 Two 1 2
• Node内側の木の初期化の最後を除くすべて
• Node内部ツリーの初期化の最後の接頭辞

したがってFingerTree (Node a)、内部ツリーのinitを取得することによって取得されたそれぞれは、にマップされます。これには、の最後のノードのinitごとNode (FingerTree a)にが含まFingerTreeれますFingerTree (Node a)。

だから、例えば、Single (Node2 3 4)抽出された最後のノードと、に分解されるEmptyとNode2 3 4、得られたですNode (FingerTree a)

Node2 
   (Deep (Two 1 2 {- prefix of original tree -}) 
         Empty 
         (One 3 {- first prefix of Node2 3 4 -}))
   (Deep (Two 1 2) 
         Empty 
         (Two 3 4 {- second prefix of Node2 3 4 -}))

そして、内部ツリーの他の接頭辞についてはDeep (One (Node2 3 4)) Empty (One (Node2 5 6))、最後Nodeを抽出するSingle (Node2 3 4)と剰余と抽出されたノードNode2 5 6が得られるため、結果はNode (FingerTree a)次のようになります。

Node2
   (Deep (Two 1 2 {- prefix of original tree -})
         (Single (Node2 3 4) {- init of the inner tree minus the last Node -})
         (One 5 {- first prefix of Node2 5 6 -})
   (Deep (Two 1 2 {- prefix of original tree -})
         (Single (Node2 3 4) {- init of the inner tree minus the last Node -})
         (Two 5 6 {- second prefix of Node2 5 6 -}))

したがって、これはFingerTree (Node a)、内部ツリーの単一の初期化である、をNode (FingerTree a)。に変換する操作です。したがって、内部ツリーのinitをとして再帰的に取得したFingerTree (FingerTree (Node a))後、この関数をそれらにマップして、を取得しますFingerTree (Node (FingerTree a))。これはまさに私たちが望んでいたことです。それは全体の初期化の内側の木です。

サフィックス

最後に、で構成される元のツリーの初期化があります

• 元のプレフィックス
• 元の内側の木
• 元のツリーの接尾辞の各初期化

これらは、initのツリーの接尾辞の数字になります。initsDigit (Two 7 8)を返しますTwo (One 7) (Two 7 8)。基本的には、\sf -> Deep pr m sfこれをマッピングするだけで、

Two 
   (Deep (Two 1 2 {- original -})
         (Deep (One (Node2 3 4)) Empty (One (Node2 5 6)) {- original -})
         (One 7 {- first init of original suffix digit -}))
   (Deep (Two 1 2 {- original -})
         (Deep (One (Node2 3 4)) Empty (One (Node2 5 6)) {- original -})
         (Two 7 8 {- second init of original suffix digit -})) 

したがって、これはコードの編成方法とはまったく異なります。私たちは、から機能を説明してきたFingerTree aのFingerTree (FingerTree a)が、実際の実装は、本質的であることに加えてfmap、我々は常に何らかの形で要素をマッピングする必要が終わるので-それはちょうどnewtypesを包んだ場合でも。しかし、これは基本的に私たちが行っていることです。