= Solution
Use the source's constructor order: left subtree, root value, right subtree.
``
data Tree a = Tree (Tree a) a (Tree a) | Empty
foldTree :: (b -> a -> b -> b) -> b -> Tree a -> b
foldTree node empty Empty = empty
foldTree node empty (Tree l x r) =
node (foldTree node empty l) x (foldTree node empty r)
unfoldTree :: (s -> Maybe (s,a,s)) -> s -> Tree a
unfoldTree next seed = case next seed of
Nothing -> Empty
Just (ls,x,rs) ->
Tree (unfoldTree next ls) x (unfoldTree next rs)
``
A <tree fold> replaces the two constructors by an algebra on already folded children. A <tree unfold> expands a seed either into the empty tree or into a root value and two new seeds. The definitions themselves work on arbitrary binary trees; preserving the <binary search tree> ordering requires the supplied algebra or seed expansion to respect its bounds.
Back to article page
