了解 Haskell 中的结构共享
Understanding Structure Sharing in Haskell
在 Liu 和 Hudak 的论文 "Plugging a Space Leak with an Arrow" 中，声称这会导致 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
如您所见，我的展开看起来几乎完全相同，并且似乎暗示两者的二次行为。以某种方式在后一个定义中设置了结构共享并重用了早期的结果，但它看起来很神奇。谁能详细说说？
松散地说：在 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，但是访问的部分已经计算好了。不需要重新计算。此强制的效果是用 n+1:map (+1) ns' 替换 map (+1) ns，其中 ns' 是指向 ns 的（现在已知的）第二个元素的指针。因此，在我们继续的过程中，我们构建了一个列表，其最后一块总是有点循环。
要理解这一点，我们需要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
我们将为计算 0 + 1 和 map (+1) ns0 引入新的变量名称 n1 和 ns1，最右边的 : 构造函数的参数。
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
我们将为计算 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 所描述的，我们只在列表的 end 处处理 "little circular bit"。
如果我们强制保留列表中的任何值，所有引用它的剩余 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 的 all 替换为刚刚计算的值，而忘记那些变量名。
successors 0 = 0 : 1 : 2 : ns2
where
ns2 = n3 : ns3
n3 = 2 + 1 -- n3 will reuse n2
ns3 = map (+1) ns2
当 n3 被强制使用时，它将使用已知的 n2 结果 (2)，而前两个加法将永远不会再进行。
在 Liu 和 Hudak 的论文 "Plugging a Space Leak with an Arrow" 中，声称这会导致 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
如您所见，我的展开看起来几乎完全相同，并且似乎暗示两者的二次行为。以某种方式在后一个定义中设置了结构共享并重用了早期的结果，但它看起来很神奇。谁能详细说说？
松散地说：在 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，但是访问的部分已经计算好了。不需要重新计算。此强制的效果是用 n+1:map (+1) ns' 替换 map (+1) ns，其中 ns' 是指向 ns 的（现在已知的）第二个元素的指针。因此，在我们继续的过程中，我们构建了一个列表，其最后一块总是有点循环。
要理解这一点，我们需要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
我们将为计算 0 + 1 和 map (+1) ns0 引入新的变量名称 n1 和 ns1，最右边的 : 构造函数的参数。
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
我们将为计算 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 所描述的，我们只在列表的 end 处处理 "little circular bit"。
如果我们强制保留列表中的任何值，所有引用它的剩余 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 的 all 替换为刚刚计算的值，而忘记那些变量名。
successors 0 = 0 : 1 : 2 : ns2
where
ns2 = n3 : ns3
n3 = 2 + 1 -- n3 will reuse n2
ns3 = map (+1) ns2
当 n3 被强制使用时，它将使用已知的 n2 结果 (2)，而前两个加法将永远不会再进行。