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

David Menendez dave at zednenem.com
Sat May 3 02:21:40 EDT 2008


On Thu, May 1, 2008 at 4:10 PM, Daniil Elovkov
<daniil.elovkov at googlemail.com> wrote:
> Felipe Lessa wrote:
>
> > On Thu, May 1, 2008 at 9:44 AM, Felipe Lessa <felipe.lessa at gmail.com>
> wrote:
> >
> > > On Thu, May 1, 2008 at 9:32 AM, Edsko de Vries <devriese at cs.tcd.ie>
> wrote:
> > >  >  So then the question becomes: what *is* the best way to write this
> function?
> > >
> > >  I guess it would be simpler to have the counter on the data type and a
> > >  smart branch constructor:
> > >
> >
> > Under more careful analysis, it seems I just moved the stack overflow
> > from the counter function to the generator =). Modifying the data type
> > to
> >
> >
> > > data Tree = Leaf Integer | Branch !Integer Tree Tree
> > >
> >
> > also won't work in this example (although it seems to fail earlier).
> > However, I'd expect the data type above to work nicely with most real
> > applications (that doesn't construct the entire tree in one go), such
> > as Data.Map[1].
> >
> > But the answer to your original question really seems to be using an
> > explicit stack created in the heap. This technique is used in Data.Map
> > in a certain case[2] and, although has received a lot of attention on
> > a thread that sparked some time ago (I think it was [3]) for being
> > merely a workaround over the limited stack, it seems to me it's a
> > compulsory workaround for the time being when working with problems
> > like yours.
> >
> >
>
>  I think that consuming heap instead of stack is the best we can do.
>
>  I may be wrong, but it seems to be more or less impossible to traverse a
> tree in constant memory. Well, if the tree structure doesn't have back links
> (apart from left, right).

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

For something like counting, we can simplify considerably because we
don't need to retain the already-traversed portion of the tree.

  acountZ :: Tree -> Integer
  acountZ t = down t [] 0
    where
    down (Branch l r) p i = down l (r:p) i
    down (Leaf _) (p:ps) i = down p ps $! i + 1
    down (Leaf _) [] i = i + 1

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


More information about the Haskell-Cafe mailing list