[Haskell-cafe] Trees
Don Stewart
dons at galois.com
Mon Dec 3 02:23:38 EST 2007
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
More information about the Haskell-Cafe
mailing list