 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2018/functional-programming-design-and-analysis-of-algorithms/1/d/solution

Replace the leaf data constructor by the constant one and the internal data constructor by addition with one extra node:

size :: Tree a -> Int
size = fold (const 1) (\m n -> 1 + m + n)

The two defining equations of the tree fold become exactly the two equations for the recursive node count.

 New to topics? Read the docs here!