dons at galois.com
Mon Dec 3 02:23:38 EST 2007
> 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
More information about the Haskell-Cafe