= Solution
For the paper's <leaf-labelled binary tree>, the combining operation receives the results of the two subtrees, and the other argument handles a leaf:
``
foldTree :: (a -> b) -> (b -> b -> b) -> Tree a -> b
foldTree f g (One x) = f x
foldTree f g (Two l r) = g (foldTree f g l) (foldTree f g r)
``
Its constructor equation is \b[`foldTree One Two = id`]. More generally, a <function> `h` satisfying `h (One x) = f x` and `h (Two l r) = g (h l) (h r)` equals `foldTree f g` on finite <trees>, by <structural induction>. This is the <tree fold> specialized to a datatype with labels only at leaves, rather than at internal nodes.
Back to article page
