ex-rec-sol

# Differences

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

 — ex-rec-sol [2015/10/08 15:20] (current) Line 1: Line 1: + ====== LiP assignment #2: solutions ====== + + + ===== 1. Arithmetic functions defined by recursion ===== + + + let iszero n = (n=0);; + + let succ n = n+1;; + + let pred n = if n<=0 then 0 else n-1;; + + let rec leq n m = if (iszero n) then true + else if (iszero m) then false + else leq (pred n) (pred m);; + + let eq n m = (leq n m) && (leq m n);; + + let rec add n m = if (iszero n) then m + else succ (add (pred n) m);; + + let rec sub n m = if (leq n m) then 0 + else succ (sub (pred n) m);; + + let rec mul n m = if (iszero n) then 0 + else add m (mul (pred n) m);; + + let rec pow n m = if (iszero m) + then 1 else mul n (pow n (pred m));; + + let rec ack m n = if (iszero m) then (succ n) + else if (not (leq m 0)) && (iszero n) then ack (pred m) 1 + else ack (pred m) (ack m (pred n));; + ​ + + \\ + + + ===== 2. Euclid'​s algorithm for GCD ===== + + + let rec gcd n m = + if n=0 then m else + if m=0 then n else + if n>m then gcd (n-m) m else + gcd n (m-n);; ​ + ​ + + Using guard expressions:​ + + let rec gcd n m = match (n,m) with + (0,m) -> m + | (n,0) -> n + | (n,m) when n>​m ​ -> gcd (n-m) m + | _ -> gcd n (m-n);; + ​ + + \\ + + ===== 3. Exponential ===== + + + let rec exp x = function + 0 -> 1 + | n when n mod 2 = 0  -> let y = exp x (n/2) in y*y + | n when n mod 2 <> 0 -> let y = exp x ((n-1)/2) in y*y*x;; + ​ + + The compiler produces a warning, because it is not able to infer that + the three pattern matching cases are exhaustive. + + To stop the compiler from complaining,​ you can use the wildcard ''​_''​ + in the last case: + + let rec exp x = function + 0 -> 1 + | n when n mod 2 = 0 -> let y = exp x (n/2) in y*y + | _ as n -> let y = exp x ((n-1)/2) in y*y*x;; + ​ + + \\ + + + ===== 4. Tail recursive absolute value ===== + + + let abs x = + let rec abs2 x acc = + if x=0 then acc + else if x>0 then abs2 (x-1) (1+acc) + else abs2 (x+1) (1+acc) + in abs2 x 0;; + ​ + + \\ + + + ===== 5. Goldbach'​s conjecture ===== + + + let isprime n = + let rec hasdivsq n b = + if b*b > n then false + else if n mod b = 0 then true + else hasdivsq n (b+1) + in + if n<=1 then false + else not (hasdivsq n 2);; + + + let rec nextprime p = + if isprime (p+1) then p+1 + else nextprime (p+1);; + + let rec prime n = + if n=1 then 2 + else let p' = prime (n-1) in nextprime p';; + + let goldbach_log n p q = + print_string ((string_of_int n) ^ " = " ^ (string_of_int p) ^ " + " ^ (string_of_int q) ^ "​\n"​);;​ + + let rec sum_two_primes n p q = + if n = p+q then ((goldbach_log n p q); true) + else let q' = nextprime q in + if p+q' <= n then sum_two_primes n p q' + else let p' = nextprime p in + if p'​+p'​ <= n then sum_two_primes n p' p' + else false;; + + let goldbach = fun () -> + let rec goldbach_rec c = + (sum_two_primes c 2 2) && goldbach_rec (c+2) + in goldbach_rec 4;; + + goldbach ();; + ​ + + \\