User Tools

Site Tools


ex-rec

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

ex-rec [2015/10/08 15:20]
ex-rec [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== LiP assignment #2 ======
 +
 +===== 1. Arithmetic functions defined by recursion =====
 +
 +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<​sup>​m</​sup>''​)
 +  - ''​ack:​ int -> int -> int'',​ the [[wp>​Ackermann_function|Ackermann function]]
 +
 +\\
 +
 +===== 2. Euclid'​s algorithm for GCD ===== 
 +Write a function ''​gcd:​ int -> int -> int''​ that computes the GCD between two natural numbers, using [[wp>​Euclid_algorithm|Euclid'​s algorithm]].
 +
 +\\
 +
 +===== 3. Exponential ===== 
 +
 +Write a function ''​exp : int -> int -> int''​ such that ''​exp n x = x<​sup>​n</​sup>''​. Exploit the fact that
 +x<​sup>​2n</​sup>​ = (x<​sup>​n</​sup>​)<​sup>​2</​sup>,​ and
 +x<​sup>​2n+1</​sup>​ = (x<​sup>​n</​sup>​)<​sup>​2</​sup>​ 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:
 +<code ocaml>
 +let rec abs x = 
 +  if x=0 then 0
 +  else if x>0 then 1 + abs (1-x)
 +  else 1 + abs (-1-x);;
 +</​code>​
 +
 +\\
 +
 +===== 5. Goldbach'​s conjecture =====
 +
 +Write a [[wp>​Prime_number|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 [[wp>​Goldbach'​s_conjecture|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)