ex-rec

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

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)