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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
