Data.Sequence 中的 inits 和 tails 如何工作？

Question

Louis Wasserman 在 Data.Sequence 中编写了 inits 和 tails 的当前实现。他表示它们非常高效，事实上，只要看一下代码，我就可以看到无论它们在做什么，它们都以干净、自上而下的方式进行，这往往会为惰性树带来良好的性能。不幸的是，我无法真正了解他们正在做的事情。谁能帮帮我？代码有点长，不过可以在Hackage.

上找到

Answer 1

是我！

我认为最好的方法可能是通过一个例子来工作。一起来吧...

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

这是一个序列，稍微简化了（例如，省略了 Elem 包装器）。

让我们对此进行初始化；尾巴基本上是对称的。我们的递归算法将省略空的 init，只包括非空的东西。

前缀

所以 inits 的前缀数字本质上是用 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))

所以这是整个事情的前两个初始值，这个数字将成为inits结果的前缀数字。（除了我们要在完成所有操作后添加空序列，但我们暂时忽略它。）

内树

现在让我们把内部树的 inits 当作一个 FingerTree (Node a) -- 我们还不打算拆开节点，它只是一个 two-element FingerTree包含两个节点。我不打算做这个的细节，它只是通过相同的算法递归，我只是要神奇地达到结果

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

所以这些是内部树的初始化。这些如何对应于外部树的初始化？内层树的每个init对应一棵包含

的树

原始树的前缀数字，Two 1 2
内部树初始化的最后Node除外
内层树init的最后Node的一些前缀

因此，通过获取内部树的 init 获取的每个 FingerTree (Node a) 将映射到一个 Node (FingerTree a)，其中包含一个 FingerTree 用于 [=18] 中最后一个节点的每个 init =].

所以例如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))，这正是我们想要的；它是整个事物的 inits 的内部树。

后缀

最后还有原树的init组成

原前缀
原始内树
原树后缀的每个init

这些就成为init树的后缀位。 initsDigit (Two 7 8) returns 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，因为我们最终总是需要以某种方式映射元素——即使它是只是包装新类型。但这基本上就是我们正在做的。

Data.Sequence 中的 inits 和 tails 如何工作？

How do inits and tails work in Data.Sequence?

haskell

data-structures

sequence