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.
--Adrian
PGP.sig
Description: Signierter Teil der Nachricht
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
