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