User Tools

Site Tools


ex-rec-sol

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 ();;


ex-rec-sol.txt · Last modified: 2015/10/08 15:20 (external edit)