理解Haskell中的结构共享

Question

在Liu和Hudak撰写的"用箭头堵塞空间泄漏"一文中,声称这会导致O(n ^ 2)运行时行为(用于计算第n项):

 successors n = n : map (+1) (successors n)

虽然这给了我们线性时间:

successors n = let ns = n : map (+1) ns
               in ns

.这句话肯定是正确的,因为我可以使用GHCi轻松验证.但是,我似乎无法理解为什么,以及在这种情况下结构共享如何帮助.我甚至试图写出计算第三学期的两个扩展.

这是我尝试的第一个变体:

successors 1 !! 2
(1 : (map (+1) (successors 1))) !! 2
     (map (+1) (successors 1)) !! 1
     (map (+1) (1 : map (+1) (successors 1))) !! 1
     2 : (map (+1) (map (+1) (successors 1))) !! 1
         (map (+1) (map (+1) (successors 1))) !! 0
         (map (+1) (map (+1) (1 : map (+1) (successors 1)))) !! 0
         (map (+1) (2 : map (+1) (map (+1) (successors 1)))) !! 0
         3 : map (+1) (map (+1) (map (+1) (successors 1))) !! 0
         3

第二个:

successors 1 !! 2
(let ns = 1 : map (+1) ns in ns) !! 2
(1 : map (+1) ns) !! 2
     map (+1) ns !! 1
     map (+1) (1 : map (+1) ns) !! 1
     2 : map (+1) (map (+1) ns) !! 1
         map (+1) (map (+1) ns) !! 0
         map (+1) (map (+1) (1 : map (+1) ns)) !! 0
         map (+1) (2 : map (+1) (map (+1) ns)) !! 0
         3 : map (+1) (map (+1) (map (+1) ns)) !! 0
         3

如你所见,我的扩展看起来几乎完全相同,似乎暗示两者的二次行为.不知何故,结构共享在后一个定义中设置并重用早期的结果,但它看起来很神奇.谁能详细说明？

Answer 1

宽泛地说:你被允许假装,在定义ns,那ns已经完全评估.所以我们实际得到的基本上是

successors n = let ns = n : map (+1) [n,n+1,n+2,n+3,n+4,...]

你只需要计算这个的成本map.

让我们来看看这个操作.

ns = n : map (+1) ns

这是做什么的？好吧,它分配一些内存来保存ns,并在其中存储一个(:)指向值的构造函数n和一个表示"thunk" 的构造函数map (+1) ns.但是那个thunk代表ns了指向同一个内存持有的指针ns!所以我们实际上在内存中有一个循环结构.当我们要求第二个元素时ns,那个thunk是强制的.这涉及访问ns,但已经计算了访问的部分.它不需要再次计算.这种强制的效果是替换map (+1) ns为n+1:map (+1) ns',ns'指向(现在已知的)第二个元素的指针ns.因此,当我们继续时,我们构建一个列表,其最后一块总是一个小圆点.

Answer 2

要理解这一点,我们需要定义 map

map _ []     = []
map f (x:xs) = f x : map f xs

我们将计算successors 0,假装结果列表的主干在我们计算它时被强制执行.我们将从绑定n开始0.

successors 0 = let ns = 0 : map (+1) ns 
               in ns

我们坚持计算的结果 - 在构造函数let或where绑定的(非严格)字段中,我们实际上存储了一个thunk,它将在评估thunk时获取计算结果的值.我们可以通过引入一个新的变量名来代表这个占位符.对于map (+1) ns放置在:构造函数尾部的最终结果,我们将引入一个名为的新变量ns0.

successors 0 = let ns = 0 : ns0 where ns0 = map (+1) ns 
               in ns

第一次扩张

现在让我们扩大

map (+1) ns

使用的定义map.我们从let刚刚写的绑定中知道:

ns = 0 : ns0 where ns0 = map (+1) ns

因此

map (+1) (0 : ns0) = 0 + 1 : map (+1) ns0

当第二个项目被强制时,我们有:

successors 0 = let ns = 0 : ns0 where ns0 = 0 + 1 : map (+1) ns0
               in ns

我们不再需要ns变量了,所以我们将其删除以清理它.

successors 0 = 0 : ns0 where ns0 = 0 + 1 : map (+1) ns0

我们将介绍新的变量名称n1,以及最右边构造函数ns1的计算0 + 1和 map (+1) ns0参数:.

successors 0 = 0 : ns0
                   where
                       ns0 = n1    : ns1
                       n1  = 0 + 1
                       ns1 =         map (+1) ns0

第二次扩张

我们扩大map (+1) ns0.

map (+1) (n1 : ns1) = n1 + 1 : map (+1) ns1

在列表的脊椎中的第三个项目(但还没有它的值)被强制之后,我们有:

successors 0 = 0 : ns0
                   where
                       ns0 = n1    : ns1
                       n1  = 0 + 1
                       ns1 =         n1 + 1 : map (+1) ns1

我们不再需要ns0变量了,所以我们将其删除以清理它.

successors 0 = 0 : n1 : ns1
                   where
                       n1  = 0 + 1
                       ns1 = n1 + 1 : map (+1) ns1

我们将介绍新的变量名称n2,以及最右边构造函数ns2的计算n1 + 1和 map (+1) ns1参数:.

successors 0 = 0 : n1 : ns1
                   where
                       n1  = 0 + 1
                       ns1 = n2     : ns2
                       n2  = n1 + 1
                       ns2 =          map (+1) ns1

第三次扩张

如果我们再次重复上一节中的步骤

successors 0 = 0 : n1 : n2 : ns2
                   where
                       n1  = 0 + 1
                       n2  = n1 + 1
                       ns2 = n3     : ns3
                       n3  = n2 + 1
                       ns3 =          map (+1) ns2

这显然在列表的脊柱中线性增长,并且在thunk中线性地增长以计算列表中保存的值.正如dfeuer所描述的那样,我们只是在处理列表末尾的"小圆点" .

如果我们强制列表中保留的任何值,则引用它的所有剩余thunk现在将引用已经计算的值.例如,如果我们强制n2 = n1 + 1它将强制n1 = 0 + 1 = 1,和n2 = 1 + 1 = 2.列表看起来像

successors 0 = 0 : n1 : n2 : ns2
                   where
                       n1  = 1           -- just forced
                       n2  = 2           -- just forced
                       ns2 = n3     : ns3
                       n3  = n2 + 1
                       ns3 =          map (+1) ns2

我们只做了两次补充.由于计算结果是共享的,因此永远不会再次计数最多2的加法.我们可以(免费)用刚刚计算出的值替换所有的n1s和n2s,并忘记那些变量名.

successors 0 = 0 : 1 : 2 : ns2
                   where
                       ns2 = n3   : ns3
                       n3  = 2 + 1       -- n3 will reuse n2
                       ns3 =        map (+1) ns2

当n3被强制时它将使用n2已知的结果(2),并且前两个添加将永远不会再次完成.