Reducing the use of space to traverse the first tree

Question

In Haskell, you can make filters, amounts, etc. in infinite lists in a constant space, because Haskell only creates list nodes if necessary, and garbage collects them with which it ends.

I would like this to work with endless trees.

Below is a pretty dumb program that generates an infinite binary tree with nodes representing natural numbers.

Then I wrote a function that makes the first pass through the depth of this tree, spitting out nodes at a certain level.

Then I made a quick sum on nodes shared by 5.

Theoretically, this algorithm can be implemented in the space O(n) for a tree of depth n nodes O(2^n) . Just generate the tree on the fly by deleting the nodes that you have already completed.

Haskell generates a tree on the fly, but not garbage collects nodes that it seems to be.

Below is the code, I would like to see code with a similar effect, but this does not require 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 nx = go nx 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

Your depthNTree uses 2^n space because you hold the left subtree around t1 while you go through the right subtree. A recursive call in the right subtree should not contain links to the left, as a necessary condition for a step-by-step garbage collection.

In this example, the naive version works acceptable:

 depthNTree nt = go nt where go 0 (Tree x _ _) = [x] go n (Tree _ lr) = go (n - 1) l ++ go (n - 1) r 

Now main with 24 input uses 2 MB of space, and in the original version - 1820 MB. The optimal solution here is similar to the one above, except that it uses difference lists:

 depthNTree nt = go nt [] where go 0 (Tree x _ _) = (x:) go n (Tree _ lr) = go (n - 1) l . go (n - 1) r 

This is not much faster than the version with the usual list in many cases, because with a tree depth of about 20-30 left nesting ++ not very expensive. The difference becomes more pronounced if we use large depths of the tree:

 print $ sum $ take 10 $ depthNTree 1000000 treeOne 

On my computer, this works after 0.25 s with difference lists and 1.6 s with lists.