[Haskell-cafe] Trees
Adrian Neumann
aneumann at inf.fu-berlin.de
Mon Dec 3 02:13:57 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.
--Adrian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 186 bytes
Desc: Signierter Teil der Nachricht
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071203/8c38bada/PGP.bin
More information about the Haskell-Cafe
mailing list