ex-rec

# Differences

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

 — 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''​) + - ''​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''​. Exploit the fact that + x<​sup>​2n​ = (x<​sup>​n​)<​sup>​2,​ and + x<​sup>​2n+1​ = (x<​sup>​n​)<​sup>​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 [[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)

### Page Tools 