User Tools

Site Tools


ex-rec

LiP assignment #2

1. Arithmetic functions defined by recursion

Write the following functions on natural numbers (using no recursion):

  1. iszero: int → bool, tests for equality with 0
  2. succ: int → int, computes the successor of a natural number
  3. 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.

  1. leq: int → int → bool, evaluates leq n m to true if n ≤ m, false otherwise
  2. eq: int → int → bool, evaluates to true if n = m, false otherwise
  3. add: int → int → int, computes the sum of two naturals
  4. sub: int → int → int, computes the difference of two naturals (we stipulate that sub n m = 0 if n<m)
  5. mul: int → int → int, computes the product of two natural numbers
  6. pow: int → int → int, computes the power of two natural numbers (i.e. pow n m = nm)
  7. ack: int → int → int, the Ackermann function


2. Euclid's algorithm for GCD

Write a function gcd: int → int → int that computes the GCD between two natural numbers, using Euclid's algorithm.


3. Exponential

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.


4. Tail recursive absolute value

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);;


5. Goldbach's conjecture

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)