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

Question

路易·沃瑟曼写的当前实现inits,并tails在Data.Sequence.他表示他们非常有效率,而且只是看着我能看到的代码,无论他们做什么,他们都是以干净,自上而下的方式做到这一点,这往往会导致懒树的良好表现.不幸的是,我实际上无法正视他们正在做的事情.任何人都可以帮我一把吗？代码有点长,但可以在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.(除非我们在完成所有操作后才会在前面添加空序列,但现在让我们忽略它.)

内在的树

现在让我们看一下内树的内容,将其视为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对应一个包含的树

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

因此,FingerTree (Node a)通过获取内部树的init获取的每个将映射到a Node (FingerTree a),包含FingerTreefor中的最后一个节点的每个init 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)将内树的单个init作为a的操作Node (FingerTree a).因此,以递归方式获取内树的内部作为a FingerTree (FingerTree (Node a)),我们将这个函数映射到它们上面得到a FingerTree (Node (FingerTree a)),这正是我们想要的; 它是整个事物内在的内在树.

后缀

最后,还有原始树的组成部分

• 原始前缀
• 原始的内树
• 每个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,因为我们最终总是需要以某种方式将元素映射-哪怕它只是包装newtypes.但这基本上就是我们正在做的事情.