haskell - 减少深度优先树遍历的空间使用

Question

在 Haskell 中，我们可以在常量空间中对无限列表进行过滤、求和等操作，因为 Haskell 仅在需要时生成列表节点，并且垃圾收集它完成的节点。

我希望它可以与无限树一起使用。

下面是一个相当愚蠢的程序，它生成一个无限二叉树，其节点代表自然数。

然后我编写了一个函数，对这棵树进行深度优先遍历，吐出特定级别的节点。

然后我对可被 5 整除的节点进行了快速求和。

理论上，该算法可以在 O(n) 空间中实现 n 深度树的 O(2^n)节点。只需动态生成树，删除已完成处理的节点即可。

Haskell 确实动态生成树，但不会对看起来的节点进行垃圾收集。

下面是代码，我希望看到具有类似效果的代码，但不需要 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 x = go n x id [] where
  go :: Int -> Tree -> ([Int] -> [Int]) -> [Int] -> [Int]
  go 0 (Tree x _ _) acc rest = acc (x:rest)
  go n (Tree _ left right) acc rest = t2 rest where 
    t1 = go (n - 1) left acc
    t2 = go (n - 1) right t1

main = do
  x <- getLine
  print . foldl' (+) 0 . filter (\x -> x `rem` 5 == 0) $ depthNTree (read x) treeOne

Answer 1

您的 depthNTree 使用 2^n 空间，因为在遍历右子树时，您将左子树保留到 t1 周围。右子树上的递归调用不应包含对左子树的引用，这是增量垃圾收集遍历的必要条件。

在此示例中，简单版本的工作效果可以接受:

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

现在输入 24 的 main 使用 2 MB 空间，而原始版本使用 1820 MB。这里的最佳解决方案与上面类似，只是它使用差异列表:

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

在许多情况下，这并不比普通列表版本快多少，因为树深度约为 20-30，++ 的左嵌套成本并不高。如果我们使用较大的树深度，差异会变得更加明显:

print $ sum $ take 10 $ depthNTree 1000000 treeOne

在我的计算机上，差异列表的运行时间为 0.25 秒，列表的运行时间为 1.6 秒。