User Tools

Site Tools


ex-rec-sol

Differences

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

Link to this comparison view

ex-rec-sol [2015/10/08 15:20] (current)
Line 1: Line 1:
 +====== LiP assignment #2: solutions ======
 +
 +
 +===== 1. Arithmetic functions defined by recursion =====
 +
 +<code ocaml>
 +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));;
 +</​code>​
 +
 +\\
 +
 +
 +===== 2. Euclid'​s algorithm for GCD ===== 
 +
 +<code ocaml>
 +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);; ​
 +</​code>​
 +
 +Using guard expressions:​
 +<code ocaml>
 +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);;
 +</​code>​
 +
 +\\
 +
 +===== 3. Exponential =====
 +
 +<code ocaml>
 +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;;
 +</​code>​
 +
 +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:
 +<code ocaml>
 +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;;
 +</​code>​
 +
 +\\
 +
 +
 +===== 4. Tail recursive absolute value =====
 +
 +<code ocaml>
 +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;;
 +</​code>​
 +
 +\\
 +
 +
 +===== 5. Goldbach'​s conjecture =====
 +
 +<code ocaml>
 +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 ();;
 +</​code>​
 +
 +\\
  
ex-rec-sol.txt ยท Last modified: 2015/10/08 15:20 (external edit)