在刘和哈达克的论文“用箭头填补空间泄漏”中,声称这会导致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
从你所看到的,我的扩展几乎完全相同,并且似乎都表明二次行为。不知何故,在后面的定义中结构共享开始启动并重用先前的结果,但这看起来像是魔法。有人可以详细说明吗?