[Haskell-cafe] Re: Understanding tail recursion and trees
Edsko de Vries
devriese at cs.tcd.ie
Sat May 3 12:30:01 EDT 2008
Hi,
> 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?
Edsko
More information about the Haskell-Cafe
mailing list