 Solution

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

The two constructors encode a natural number by its number of successors. Structural recursion replaces the zero constructor by zero and every successor by one addition:

convert :: Natural -> Integer
convert Zero     = 0
convert (Succ n) = 1 + convert n

convert (Succ^{n} Zero) = n

. The output uses unbounded integers, so there is no machine-word overflow.

 New to topics? Read the docs here!