[Haskell-cafe] Painting logs to get a coloured tree

[wren ng thornton]

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