minh thu wrote:
Joachim Breitner:
I thought about Zippers, but I understand that they improve _navigating_ in a Tree-like structure, or to refrence _one_ position in a tree.
But if I would deconstruct my tree to the list of _all_ locations, with
type Loc a = (Tree a, Cxt a) and then run my algorithm that returns [(Loc a, Info)], it's still not clear to me how I can combine all of these locations to get back my original Tree, annotated with the Info returned.
I guess I just repeat your last praragraph of your original mail but it seems to me you can mapAccump some 'names' on the tree, process an association list (or an IntMap) of the (name,log) then map the three again using the result. In spirits, it's the same thing than the STRef solution but it seems cleaner to me.
It might also be worth looking at Okasaki's algorithm for (breadth-first) numbering of nodes in a tree[1]. Assuming your tree doesn't have interesting invariants to maintain, a similar/inverse algorithm could be used to "unfold" a list of logs back into a tree. As minh thu says, the numbering seems like it only needs to be conceptual rather than actual. In which case you should be able to fuse the code that traverses the tree to produce logs and the code that traverses the logs to produce a tree (aka a hylomorphism, if you're familiar). The knot-tying step should only be necessary if constructing the tree from logs requires more information than whatever's local to the log itself. Of course, if global information is necessary then you probably _do_ need to actually label the tree. At least it's cleaner than STRefs since you don't need mutability. [1] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#icfp00 -- Live well, ~wren