= Solution
A <tree fold> replaces `Empty` by a seed and `Node` by a combining <function>. The combining <function> receives the already folded left subtree, the node's label and the already folded right subtree:
``
foldSTree :: (b -> a -> b -> b) -> b -> STree a -> b
foldSTree combine empty Empty = empty
foldSTree combine empty (Node left x right) =
combine (foldSTree combine empty left)
x
(foldSTree combine empty right)
``
Its <polymorphic> <type signature> is
$$
\boxed{(\beta\to\alpha\to\beta\to\beta)\to\beta\to\mathrm{STree}\ \alpha\to\beta.}
$$
The result type need not be the label type: it may be a <list>, a number or another structure. No ordering constraint is needed because this <tree fold> follows constructors without comparing labels.
Back to article page
