理解 Haskell 中的结构共享

Question

在刘和哈达克的论文“用箭头填补空间泄漏”中，声称这会导致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

从你所看到的，我的扩展几乎完全相同，并且似乎都表明二次行为。不知何故，在后面的定义中结构共享开始启动并重用先前的结果，但这看起来像是魔法。有人可以详细说明吗？

- firefrorefiddle

---

理解共享需要对图形进行操作，而在线性公式上进行操作会令人感到困惑。 - augustss

Answer 1

大致上来说：在定义ns时，你可以假装ns已经完全被评估。因此，我们实际上得到的是基本上以下内容：

松散地说：在定义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" 和表示 "map (+1) ns" 的 "thunk" 的构造函数存储在其中。但是该 "thunk" 表示 "ns" 作为指向存储 "ns" 的同一块内存的指针！因此我们实际上在内存中有一个循环结构。当我们请求 "ns" 的第二个元素时，该 "thunk" 被强制执行。这涉及访问 "ns"，但已经计算出所访问的部分。它不需要重新计算。强制执行的效果是用指向 "ns" 的第二个元素（现在已知）的指针 "ns'" 替换 "map (+1) ns"，因此随着我们的进行，我们构建的列表总是最后带有一个小的循环部分。

- dfeuer

---

谢谢你的出色回答！它对我帮助很大。我很难选择哪一个是最好的。 - firefrorefiddle

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

第二次扩展

我们对 ns0 进行了 map (+1) 扩展。

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

我们将为计算 n1 + 1 和 map (+1) ns1 引入新的变量名 n2 和 ns2，作为最右侧 : 构造函数的参数。

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，必须执行加法，但以后再也不需要执行这个操作，因为计算结果已经得出。我们可以（免费）用刚计算出的值替换n1和n2中的全部值，并忘记这些变量名。

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

当强制使用 n3 时，它将使用已知的 n2 结果（2），并且那前两个加法将不会再次执行。

- Cirdec

---

谢谢！我想我现在明白了！ - firefrorefiddle