[Haskell-cafe] Trees

[Don Stewart]

aneumann:
> Good morning,
> 
> as an exercise for my Algorithms and Programming course I have to  
> program a couple of simple functions over trees. Until now everything  
> we did in Java could be done in Haskell (usually much nicer too)  
> using the naive
> 
> > data Tree a = Leaf a | Node a [Tree a]
> 
> But now the assignments require more than a simple top-down  
> traversal. For example: given a tree t and two nodes u,v, find the  
> first common ancestor.
> In Java this is really simple, because each node has a "parent"  
> reference. That way I only need to follow those references until I  
> find the first common ancestor. This should take something like O(log  
> n) in the average case.
> 
> In Haskell however the best way I've come up with so far is doing a  
> BFS and looking for the last common node in the paths to u and v.  
> This is neither fast, nor particularly elegant.
> So how would you smart guys do it? With a Zipper? It would be nice if  
> there was an elegant solution without monads.
> 

For a cursor, with O(1) access to parents, a zipper of a Tree is really
quite nice, and fast. I'd start there. (Huet's original zipper paper is
straightforward to translate from ML, and we have zippers on the
wikibook now).

-- Don