= Solution
A <tree fold> replaces each constructor by its interpretation:
``
foldTree :: (b -> [a] -> b -> b) -> b -> Tree a -> b
foldTree combine zero Empty = zero
foldTree combine zero (Node left equal right) =
combine (foldTree combine zero left)
equal
(foldTree combine zero right)
fromTreeFold :: Tree a -> [a]
fromTreeFold = foldTree (\left equal right -> left ++ equal ++ right) []
``
<Induction> on the finite tree shows equality with `fromTree`: the empty tree produces the empty output, and the combining <function> concatenates the two correctly flattened children around the node's bucket. The result type $b$ is independent of the key type; other choices can compute a size or another summary using the same <structural recursion>.
Back to article page
