haskell - 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

最佳答案

我写了一本关于深度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 supports GC为静态值。

关于haskell - Haskell垃圾收集器如何有效地收集树木，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34433757/