 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/b/solution

Count each data constructor once, including each Two:

size :: Tree a -> Int
size (One _)   = 1
size (Two l r) = 1 + size l + size r

Structural induction verifies the count: a leaf contributes one; an internal node contributes itself and the disjoint occurrences in its two subtrees. Fully evaluating the result takes linear time in the number of nodes. This type signature uses machine Int as usual in the examination; Integer avoids overflow for arbitrarily large inputs.

 New to topics? Read the docs here!