5. Addition And Multiplication

The same representation can be used for other functions.

Consider addition.

There are several possible recursive definitions of addition. We will use one that reduces the first argument.

The table is:

The base cases are straightforward.

Adding zero to zero gives zero.

Adding zero to suc(l) gives suc(l).

Adding suc(k) to zero gives suc(k).

The final cell contains the recursive case:

$ suc(k)+suc(l)\mapsto suc(k+suc(l)). $

The recursive addition inside the outer suc has first argument k.

The original first argument was suc(k).

So one constructor has been removed.

Consider:

$ 2+2. $

Written using constructors:

$ suc(suc(zero))+suc(suc(zero)). $

Applying the recursive case gives:

$ suc(suc(zero)+suc(suc(zero))). $

Applying it again:

$ suc(suc(zero+suc(suc(zero)))). $

The base case now applies:

$ suc(suc(suc(suc(zero)))). $

That is 4.

The table places the base cases and the recursive direction in one representation.

Multiplication can be defined similarly:

If either argument is zero, the result is zero.

The recursive case is:

$suc(k)\times suc(l)\mapsto(k\times suc(l))+suc(l).$

Again, the multiplication on the right has a smaller first argument.

The original problem contained suc(k).

The recursive multiplication contains k.

The definition reduces the multiplication structurally while using addition to construct the result.