(* $Id$ *)

(**** Exercice 1 ****)

(* Q1 *)

let est_pytha x y z = x * x + y * y = z * z;;
  
(* Q2 *)

let rec trouve_pytha_aux x y z =
  if (est_pytha x y z) then (x, y, z)
  else if y * y >= z * z then raise Not_found
  else trouve_pytha_aux x (y + 1) z;;

let trouve_pytha x z = trouve_pytha_aux x 1 z;;

let _ = trouve_pytha 3 5;;
let _ = trouve_pytha 2 8;;
let _ = trouve_pytha 9 41;;

(* Q3 *)

let rec genere_pytha_aux m n =
  let a = 2 * n + 1
  and b = 2 * n * n + 2 * n
  and c = 2 * n * n + 2 * n + 1 in
  if (a <= m && b <= m && c <= m) then
    (a, b, c)::(genere_pytha_aux m (n + 1))
  else [];;

let genere_pytha m = genere_pytha_aux m 1;;

let _ = genere_pytha 50;;

(**** Exercice 2 ****)

type nombre =
  | Ent of int
  | Rat of (int * int);;

(* Q1 *)

let add_rat = function
  | Rat (x1, y1), Rat (x2, y2) -> Rat (x1 * y2 + x2 * y1, y1 * y2)
  | _ -> failwith "add_rat";;

let _ = add_rat (Rat (1, 2), Rat (3, 4));;

(* Q2 *)

let rec somme_nombre = function
  | [] -> Rat (0, 1)
  | (Ent e)::tl -> add_rat (Rat (e, 1), somme_nombre tl)
  | (Rat r)::tl -> add_rat (Rat r, somme_nombre tl);;

let ln1 = [Ent 2; Rat (1, 2); Rat (3, 4)];;

let _ = somme_nombre ln1;;

(* Q3 *)

exception Inversion of nombre;;

let rec inverse_nombre = function
  | [] -> []
  | (Ent e)::tl ->
     if e = 0 then raise (Inversion (Ent e))
     else (Rat (1, e))::(inverse_nombre tl)
  | (Rat (x, y))::tl ->
     if x = 0 then raise (Inversion (Rat (x, y)))
     else (Rat (y, x))::(inverse_nombre tl);;

let ln2 = [Ent 2; Rat (1, 2); Ent 0; Rat (3, 4)];;
let ln3 = [Ent 2; Rat (1, 2); Ent 0; Rat (3, 4)];;

let _ = inverse_nombre ln1;;
let _ = inverse_nombre ln2;;
let _ = inverse_nombre ln3;;

(* Q4 *)

let simplifie_nombre l =
  List.fold_right (fun e a ->
    match e with
    | Ent 0 -> a
    | Rat (0, _) -> a
    | Rat (x, 1) -> (Ent x)::a
    | _ -> e::a) l [];;

let ln4 = [Ent 2; Rat (3, 1); Ent 0; Rat (2, 3); Rat (0, 4)];;

let _ = simplifie_nombre ln4;;

(**** Exercice 3 ****)

type 'a set =
  | Empty
  | Add of 'a * 'a set;;

(* Q1 *)

let rec mem x = function
  | Empty -> false
  | Add (e, tl) ->
     if x = e then true
     else mem x tl;;

let e1 = Add (1, Add (3, Add (2, Empty)));;

let _ = mem 2 e1;;
let _ = mem 4 e1;;

(* Q2 *)

let rec union e1 e2 =
  match e1 with
  | Empty -> e2
  | Add (e, tl) ->
     if mem e e2 then union tl e2
     else Add (e, union tl e2);;

let e2 = Add (3, Add (4, Add (5, Empty)));;

let _ = union e1 e2;;

(* Q3 *)

let rec inter e1 = function
  | Empty -> Empty
  | Add (e,tl) ->
     if mem e e1 then Add (e, inter e1 tl)
     else inter e1 tl;;

let _ = inter e1 e2;;