[Haskell-cafe] Trees

[Stefan O'Rear]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20071202/3ab6d20d/attachment.bin