[Haskell-cafe] Re: Understanding tail recursion and trees

[David Menendez]

On Sat, May 3, 2008 at 12:30 PM, Edsko de Vries <devriese at cs.tcd.ie> wrote:
>
>  > I think Huet's Zipper is intended to solve this sort of problem.
>  >
>  >   data Path = Top | BranchL Path Tree | BranchR Tree Path
>  >   type Zipper = (Path, Tree)
>  >
>  >   openZipper :: Tree -> Zipper
>  >   openZipper t = (Top, t)
>  >
>  > Conceptually the zipper is a tree with one subtree selected. You can
>  > move the selection point with the (partial) functions defined below.
>  >
>  >   downL, downR, up :: Zipper -> Zipper
>  >   downL (p, Branch l r) = (BranchL p r, l)
>  >   downR (p, Branch l r) = (BranchR l p, r)
>  >   up (BranchL p r, l) = (p, Branch l r)
>  >   up (BranchR l p, r) = (p, Branch l r)
>  >
>  > Note that these functions just shuffle existing subtrees around.
>  > Depending on your traversal pattern, these can run in roughly constant
>  > space.
>  >
>  > Using the zipper, we can define functions that traverse the entire
>  > tree and return a new tree:
>  >
>  >   number :: Tree -> Tree
>  >   number t = down Top t 0
>  >     where
>  >     down p (Leaf _)     n = up p (Leaf n) $! n + 1
>  >     down p (Branch l r) n = down (BranchL p r) l n
>  >
>  >     up Top t n = t
>  >     up (BranchL p r) l n = down (BranchR l p) r n
>  >     up (BranchR l p) r n = up p (Branch l r) n
>
>  Please correct me if I'm wrong, but doesn't the the size of the zipper
>  grow every time we move down the left branch? I.e., by the time we reach
>  the leaf, we'll have a zipper (BranchL (BranchL ..)) of size the depth
>  of the tree? Or am I missing something?

If there are no other references to the tree, then each time a new
node in the zipper is created, the corresponding node in the original
tree can be discarded. Typically, the garbage won't be collected
immediately, so there will be some growth in actual memory usage, but
this will be bounded.

If there are other references to the tree, then the nodes in the
original tree cannot be reclaimed. Even so, the zipper never grows in
size beyond the longest path from root to leaf in the tree.

-- 
Dave Menendez <dave at zednenem.com>
<http://www.eyrie.org/~zednenem/>