Write the following functions on natural numbers (using no recursion):
iszero: int → bool, tests for equality with 0
succ: int → int, computes the successor of a natural number
pred: int → int, computes the predecessor of a natural number (we stipulate that
pred 0 = 0).
then, use them to define (using recursion) the functions at items 1 to 7. Note that you cannot use any arithmetical operator (such as +, -, <, > etc…) but only the functions that you have already defined, at previous items.
leq: int → int → bool, evaluates
leq n mto true if
n ≤ m, false otherwise
eq: int → int → bool, evaluates to true if
n = m, false otherwise
add: int → int → int, computes the sum of two naturals
sub: int → int → int, computes the difference of two naturals (we stipulate that
sub n m = 0if
mul: int → int → int, computes the product of two natural numbers
pow: int → int → int, computes the power of two natural numbers (i.e.
pow n m = nm)
ack: int → int → int, the Ackermann function
Write a function
gcd: int → int → int that computes the GCD between two natural numbers, using Euclid's algorithm.
Write a function
exp : int → int → int such that
exp n x = xn. Exploit the fact that
x2n = (xn)2, and
x2n+1 = (xn)2 x.
Hint. Use pattern matching with guards for a cleaner definition.
Write a tail-recursive version of the following function, that computes the absolute value of an integer:
Write a primality test for natural numbers, that is a function
isprime: int → bool such that
isprime n evaluates to
n is prime,
Then, write a function
goldbach: unit → bool such that
goldbach ()evaluates to false, if the Goldbach's conjecture is false
goldbach ()diverges (i.e. it does not terminate), if the Goldbach's conjecture is true