3 Dec
2007
3 Dec
'07
10:36 a.m.
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]).