On Mon, Dec 03, 2007 at 08:13:57AM +0100, Adrian Neumann wrote: > 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.
It should be noted that this is a question of style, not language, and
the Java solution translates to Haskell:
data Tree a = Node { idn:: Int, val:: a, parent:: Maybe (Tree a), children::
[Tree a] }
You can make this efficiently mutable, but only at the cost of making it
ephemeral, a natural property of Java's data structures but frowned on
in our culture.
Stefan
signature.asc
Description: Digital signature
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
