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