[Haskell-cafe] Trees

[Matthew Brecknell]

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]).