[Haskell-cafe] Re: Seeking advice about monadic traversal functions
apfelmus at quantentunnel.de
Fri Apr 2 13:39:13 EDT 2010
Darryn Reid wrote:
> 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.).
More information about the Haskell-Cafe