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]). _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
