[Haskell-cafe] Trees

[Yitzchak Gale]

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.

Perhaps you meant:

data Node a = Node { idn:: Int, val:: a, parent:: Maybe Int, children:: [Int] }
type Tree a = Data.IntMap (Node a)

-Yitz