Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Functional programming, design and analysis of algorithms / 2 / c / 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 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.