Haskell垃圾收集器如何有效地收集树木 [英] How the Haskell garbage collector efficiently collects trees

问题描述

这个代码来自这个问题下面复制的很好，只需要 O（n）空间对深度树 n O（2 ^ n）节点。这非常好，垃圾收集器似乎在清理已处理的树方面做得很好。

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

  import Data.List（foldl'）
 
 data Tree = Tree Int树树
 
树n =树n（树（2 * n））（树（2 * n + 1））
 tree1ne =树1 
 
 depthNTree nt = go nt []其中
为0（Tree x _ _）=（x :) 
 go n（Tree _ lr）= go（n  -  1） l。 go（n  -  1）r 
 
 main = do 
 x < -  getLine 
 print。 foldl'（+）0。过滤器（\ x  - > x`rem` 5 == 0）$ depthNTree（read x）treeOne 
  

解决方案

我写了一个树的深度为2的小小手动评估。我希望它可以说明为什么树节点可以被垃圾收集。

假设我们从这样一棵树开始：

  tree = 
 Tree 
（Tree _  -  l 
（Tree a _ _） -  ll 
（Tree b _ _）） -  lr 
（Tree _  -  r 
 c_ _） -  rl 
（Tree d _ _）） -  rr 
  

现在调用 depthNTree 2 tree ：

  go 2 tree [] 
 go 2（Tree _ lr）[] 
 go 1 l（go 1 r []）
 go 1（Tree _ ll lr）（go 1 r []）
 go 0 （go 1 r []））
 go 0（Tree a _ _）（go 0 lr（go 1 r []））
a：go 0 lr（go 1 r [ ]） -  gc可以收集ll 
a：go 0（Tree b _ _）（go 1 r []）
a：b：go 1 r [] -  gc可以收集lr，因此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可以收集rl 
a：b：c：go 0（Tree d _ _）[] 
a：b：c：d：[]  -  gc可以收集rr，因此r和树
  

请注意，由于 treeOne 是一个静态值，所以在后台必须有一些额外的机制来允许垃圾回收。幸运的是，GHC 支持GC 的静态值。

This code from the answer to this question copied below quite nicely takes only O(n) space to do a depth first traversal of a tree of depth n which contains O(2^n) nodes. This is very good, the garbage collector seems to be doing a good job of cleaning up the already processed tree.

But my question I have is, how? Unlike a list, where once we process the first element we can completely forget it, we can't scrap the root node after processing the first leaf node. We have to wait until the left half the tree is processed (because eventually we'll have to traverse down the right from the root). Also, as the root node points to the nodes below it, and so on, all the way down to the leaves, which would seem to imply that we wouldn't be able to collect any of the first half of a tree until we start on the second half (as all those nodes will still have references to them starting from the still live root node). This fortunately is not the case, but could someone explain how?

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

解决方案

I wrote a little manual evaluation of a tree to depth 2. I hope it can illustrate why tree nodes can be garbage collected along the way.

Suppose we start with a tree like this:

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

Now call 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

Note that since treeOne is a static value, there has to be some extra machinery behind the scenes to allow garbage collection of it. Fortunately GHC supports GC of static values.

这篇关于Haskell垃圾收集器如何有效地收集树木的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！