[Haskell-cafe] Re: Seeking advice about monadic traversal functions

[Heinrich Apfelmus]

Darryn Reid wrote:
> Heinrich,
> 
> Thanks for your excellent response! Indeed, it was the rebuilding of the
> tree that had me stumped. I also see the benefits of using the lift
> functions, thanks again for this insight.

My pleasure. :)

By the way, there's also another, very flexible way to rebuild the tree:
give each node a unique identifier. The traversal returns a list of
labeled nodes with their children replaced by labels, like this:

    [(1,Nil),(2,Single 'a' 3),(3,Nil),(4,Fork 1 2),...]

To rebuild the tree, simply put the list into a finite  map  and replace
identifiers by proper trees again.

However, this solution is essentially the same as using a mutable tree,
the unique identifiers represent memory addresses. That's why I sought
to reconstruct the tree from the structure of the traversal (using the
same intermediate queue data structure, etc.).


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com