如何让Haskell垃圾收集器高效地收集树形结构。

Question

这段代码取自下面这个问题的答案，它很好地完成了对深度为n的节点数为O(2^n)的树进行深度优先遍历时只占用O(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

- Clinton

---

它只存储当前正在检查的O(n)个节点，难道不是这样吗？也就是说，如果它处理了一个叶子节点，它会忘记它并用下一个叶子节点替换它。此外，Haskell以其惰性而闻名，这意味着它不会评估当前不需要的任何内容。 - Glubus

我们必须等到树的左半部分被处理完才能继续。递归使用该参数，您会注意到一种模式。 - Zeta

我曾经认为像treeOne这样的顶级绑定会防止任何垃圾回收。也许 GHC 的优化比我想象的要多。 - chi

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) [])作为一个thunk（因此不会生成任何更多的r）。

递归到go将强制执行l，所以我们会生成更多的l。但是接下来再次重复相同的步骤，该树节点立即成为垃圾，生成两个保存左右子树的子子树thunk，然后仅强制执行左侧一个。

经过n次调用后，我们将评估go 0 (Tree x _ _) = (x:)。我们生成了n对thunks，并强制执行了n个左侧thunk，使得右侧thunk留在内存中；由于右子树是未求值的thunk，它们每个占用常数空间，并且只有n个，因此总共只有O(n)的空间。现在指向这条路径的所有树节点都没有引用。

实际上，我们拥有最外层的列表构造函数（和列表的第一个元素）。强制执行更多的列表将进一步探索正在构建的组合链中的那些右子树thunk，但是n个thunk是最多的。

---

从技术上讲，您已经将对tree 1的引用绑定到全局作用域中的treeOne，因此可以保留您生成的每个节点的引用，因此您依赖于GHC注意到treeOne仅被使用一次，因此不应该被保留。

- Ben

---

这也是一个非常好的答案，但我只能接受一个。所有三个都很棒，谢谢，它们都得到了赞（并且应该得到更多）。 - Clinton

Answer 2

让我们重写go的递归部分为：

go n t = case t of
           Tree _ l r -> go (n - 1) l . go (n - 1) r

在右边的情况中，原树 t 不再存活，只有 l 和 r 存活。因此，如果我们首先进入 l，那么除了 l 本身之外，没有任何东西使树的左侧保持活动状态；r 恰好使树的右侧保持活动状态。

在递归的任何时候，存活的节点恰好是从原始树根到当前被检查节点所经过的路径切断的子树的根，这些子树尚未被处理。这些子树的数量最多为该路径的长度，因此空间使用量为 O(n)。

关键是在递归之前原树 t 变成了死树。如果您编写（表面上等效但风格不佳的）代码...

leftChild (Tree _ l r) = l
rightChild (Tree _ l r) = r

go n t = go (n - 1) (leftChild t) . go (n - 1) (rightChild t)

现在，当递归到 go (n - 1) (leftChild t) 时，在未求值的表达式 rightChild t 中仍然存在对 t 的引用。因此，空间使用现在是指数级的。

- Reid Barton

---

这也是一个非常好的答案，但我只能接受一个。所有三个都很棒，谢谢，它们都得到了赞（并且应该得到更多）。 - Clinton

Answer 3

我写了一个简单的树形结构评估手册，涉及到深度为2的问题。希望这个手册可以解释为什么树形节点可以在路上被垃圾回收。

假设我们从以下的树型结构开始：

tree =
  Tree
    (Tree _          -- l
       (Tree a _ _)    -- ll
       (Tree b _ _))   -- lr
    (Tree _          -- r
       (Tree c _ _)    -- rl
       (Tree d _ _))   -- rr

现在调用depthNTree 2 tree:

go 2 tree []
go 2 (Tree _ l r) []            
go 1 l (go 1 r [])
go 1 (Tree _ ll lr) (go 1 r [])
go 0 ll (go 0 lr (go 1 r []))
go 0 (Tree a _ _) (go 0 lr (go 1 r []))
a : go 0 lr (go 1 r [])                   -- gc can collect ll
a : go 0 (Tree b _ _) (go 1 r [])
a : b : go 1 r []                         -- gc can collect lr and thus l
a : b : go 1 (Tree _ rl rr) []
a : b : go 0 rl (go 0 rr [])
a : b : go 0 (Tree c _ _) (go 0 rr [])
a : b : c : go 0 rr []                    -- gc can collect rl
a : b : c : go 0 (Tree d _ _) []
a : b : c : d : []                        -- gc can collect rr and thus r and tree

请注意，由于treeOne是一个静态值，因此在幕后需要一些额外的机制来允许对其进行垃圾回收。幸运的是，GHC支持对静态值进行GC。

- András Kovács