haskell - 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 结果的前缀数字。 (除非我们将在完成所有操作后在前面添加空序列，但现在让我们忽略它。)

<小时/>

内部树

现在让我们获取内部树的 init，将其视为 FingerTree (Node a) -- 我们还不打算拆开节点，它只是一个二元 FingerTree包含两个节点。我不打算详细说明这一点，它只是通过相同的算法进行递归，我只是会神奇地得到结果

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

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

的树

• 原始树的前缀数字，Two 1 2
• 除了最后一个之外的所有 Node内部树的 init
• 最后一个 Node 的一些前缀内部树的 init

所以每个 FingerTree (Node a)通过内部树的 init 获取的将映射到 Node (FingerTree a) ，包含FingerTree对于 FingerTree (Node a) 中最后一个节点的每个 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) 。因此，递归获取内部树的 inits 作为 FingerTree (FingerTree (Node a)) ，我们将此函数映射到它们上以获得 FingerTree (Node (FingerTree a)) ，这正是我们想要的；它是整个事物的内部树。

<小时/>

后缀

最后，还有由组成的原始树的inits

• 原始前缀
• 原始内部树
• 原树后缀的各个init

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