-- A Tree is either a Branch with subtrees or a Leaf.
-- Both carry a String as a tag.
data Tree = Branch String [Tree] | Leaf String
deriving (Show)
findNode :: String -> Tree -> Maybe Tree
-- A function can happily walk a tree via pattern
-- matching.
findNode q t@(Leaf tag)
| tag == q = Just t
| otherwise = Nothing
findNode q t@(Branch tag subtrees)
| tag == q = Just t
| otherwise = foldl findInBranch Nothing subtrees
where
findInBranch acc subtree = case acc of
Just _ -> acc
Nothing -> findNode q subtree
allLeavesTags :: Tree -> [String]
allLeavesTags (Leaf tag) = [tag]
allLeavesTags (Branch _ subtrees) = foldl allInBranch [] subtrees
where
allInBranch acc subtree = acc ++ (allLeavesTags subtree)
t = Branch "a" [Branch "b" [Branch "c" [], Leaf "d"], Leaf "j"]
main = do
putStrLn . show $ findNode "c" t
putStrLn . show $ allLeavesTags t