[Haskell-cafe] Trees

[Derek Elkins]

On Mon, 2007-12-03 at 16:56 +0200, Yitzchak Gale wrote:
> Adrian Neumann wrote:
> >> > data Tree a = Leaf a | Node a [Tree a]
> >> 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...
> >> 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.
> 
> Stefan O'Rear wrote:
> > 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...
> 
> That looks like a tying-the-knot approach. It is interesting,
> but I don't see how it is similar to the Java. You still
> need to search for u and v somehow. And as for making
> it mutable, you can forget it; your fingers will quickly
> become weary from untying and retying all of those knots.

If made mutable, there's nothing stopping it from being exactly like the
Java approach.  It should be no more finger tiring than Java (but then
we -are- talking about Java...)