ex-rec

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 m`

to 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 = 0`

if`n<m`

)`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 = n`

)^{m}`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 = x`

. Exploit the fact that
x^{n}^{2n} = (x^{n})^{2}, and
x^{2n+1} = (x^{n})^{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:

let rec abs x = if x=0 then 0 else if x>0 then 1 + abs (1-x) else 1 + abs (-1-x);;

Write a primality test for natural numbers, that is a function `isprime: int → bool`

such that `isprime n`

evaluates to `true`

if `n`

is prime, `false`

otherwise.

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

ex-rec.txt · Last modified: 2015/10/08 15:20 (external edit)