haskell - Haskell 垃圾收集器如何有效地收集树

Question

此代码来自此 question 的答案很好地复制到下面只需要O(n)对深度树进行深度优先遍历的空间 n其中包含 O(2^n)节点。这很好，垃圾收集器似乎在清理已经处理的树方面做得很好。

但我的问题是，怎么做？与列表不同，一旦我们处理了第一个元素，我们就可以完全忘记它，我们不能在处理完第一个叶节点后废弃根节点。我们必须等到处理完树的左半部分(因为最终我们必须从根向下遍历右半部分)。此外，由于根节点指向它下面的节点，依此类推，一直到叶子，这似乎意味着在我们开始之前我们无法收集树的前半部分在后半部分(因为所有这些节点仍然会从仍然存在的根节点开始引用它们)。幸运的是，情况并非如此，但有人可以解释一下吗？

import Data.List (foldl')

data Tree = Tree Int Tree Tree

tree n = Tree n (tree (2 * n)) (tree (2 * n + 1))
treeOne = tree 1

depthNTree n t = go n t [] where
  go 0 (Tree x _ _) = (x:)
  go n (Tree _ l r) = go (n - 1) l . go (n - 1) r

main = do
  x <- getLine
  print . foldl' (+) 0 . filter (\x -> x `rem` 5 == 0) $ depthNTree (read x) treeOne

Answer 1

实际上，当您下降左子树时，您不会捕获根。

go n (Tree _ l r) = go (n - 1) l . go (n - 1) r

所以根变成了两个 thunk，组合在一起。一个持有对左子树的引用，另一个持有对右子树的引用。根节点本身现在是垃圾。

左右子树本身只是 thunk，因为树是惰性生成的，所以它们还没有消耗太多空间。

我们只评估 go n (Tree _ l r)因为我们正在评估 depthNTree n t ，即 go n t [] .所以我们立即强制这两个组成go调用我们刚刚将根变为:

(go (n - 1) l . go (n - 1) r) []
= (go (n - 1) l) ((go (n - 1) r) [])

因为这是惰性求值，所以我们先做最外层的调用，留下 ((go (n - 1) r) [])作为重击(因此不再生成 r )。

递归到 go将强制 l ，所以我们确实产生了更多。但随后我们又在下一级做同样的事情；再次，该树节点立即变成垃圾，我们生成两个持有左右子子树的 thunk，然后我们只强制左侧一个。

之后 n我们将评估的电话 go 0 (Tree x _ _) = (x:) .我们生成了n对 thunk，并强制 n左边的，右边的留在内存中；因为右子树是未评估的 thunk，它们每个都是常数空间，并且只有 n其中，所以只有 O(n)总空间。并且通向这条路径的所有树节点现在都没有被引用。

我们实际上有最外层的列表构造函数(以及列表的第一个元素)。强制更多的列表将探索那些正确的子树 thunk 进一步向下构建组合链，但永远不会超过 n其中。

从技术上讲，您已经绑定(bind)了对 tree 1 的引用。在全局范围内 treeOne ，因此实际上您可以保留对您曾经生成的每个节点的引用，因此您依赖 GHC 注意到 treeOne只使用一次，不应保留。