这段代码取自下面这个问题的答案,它很好地完成了对深度为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
treeOne
这样的顶级绑定会防止任何垃圾回收。也许 GHC 的优化比我想象的要多。 - chi