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

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

我写了一些对深度为 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。