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. --Adrian
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
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
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
Adrian Neumann:
data Tree a = Leaf a | Node a [Tree a] example: given a tree t and two nodes u,v, find the first common ancestor.
The following solves what I think is a generalisation of this problem. That is, given a tree and a predicate on its elements, return the smallest subtree containing all nodes satisfying the predicate, or Nothing if none satisfy it.
import Data.Maybe
data Tree a = Node a [Tree a]
lub :: (a -> Bool) -> Tree a -> Maybe (Tree a) lub p (Node a s) | p a = Just (Node a s) | otherwise = case mapMaybe (lub p) s of [] -> Nothing [t] -> Just t _ -> Just (Node a s)
If I understand the original problem correctly, then the appropriate predicate would just be (flip elem [u,v]).
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...)
Adrian Neumann wrote:
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.
Well, this problem doesn't make much sense in Haskell. How do you specify the subtrees u and v in the first place? Regards, apfelmus
One could alway store a node's depth at each node -- then you must search for u and v, creating a list of what nodes you found at each depth, and finally, simply compare the lists -- O(n) in the depth of u and v. Bob On 3 Dec 2007, at 08:40, apfelmus wrote:
Adrian Neumann wrote:
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.
Well, this problem doesn't make much sense in Haskell. How do you specify the subtrees u and v in the first place?
Regards, apfelmus
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Thomas Davie wrote:
apfelmus wrote
Well, this problem doesn't make much sense in Haskell. How do you specify the subtrees u and v in the first place?
One could alway store a node's depth at each node -- then you must search for u and v, creating a list of what nodes you found at each depth, and finally, simply compare the lists -- O(n) in the depth of u and v.
Huh? I mean, are u and v node labels of type a? Or are they subtrees? In any case, they aren't "pointers" into the tree. In the case of node labels, a breath first search will take O(number of nodes of depth <= min (depth u) (depth v)) steps which is O(size of the tree) in the worst case. Regards, apfelmus
participants (8)
-
Adrian Neumann -
apfelmus -
Derek Elkins -
Don Stewart -
Matthew Brecknell -
Stefan O'Rear -
Thomas Davie -
Yitzchak Gale