[Haskell-cafe] Painting logs to get a coloured tree
wren ng thornton
wren at freegeek.org
Tue Feb 10 20:32:49 EST 2009
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. 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.
More information about the Haskell-Cafe