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

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

我希望它能与无限的树一起使用。

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

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

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

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

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

下面是代码，我希望看到具有类似效果的代码，但这不需要O(2^n) space.

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

Your depthNTree uses 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

Now main输入 24 使用 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 秒。