[Haskell-cafe] Trees
Matthew Brecknell
haskell at brecknell.org
Mon Dec 3 10:36:48 EST 2007
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]).
More information about the Haskell-Cafe
mailing list