(* Chapitre 2 *)
(* Exercice 3 *)
type 'a polynome = Somme of 'a polynome * 'a polynome
	| Produit of 'a polynome * 'a polynome
	| Difference of 'a polynome * 'a polynome
	| Puissance of 'a polynome * int
	| Const of 'a
	| X;;

let p = Produit ( Somme (X, Const 2), Difference(X, Const 3));;

let monome const n = Produit( Const const, Puissance ( X, n));;

let q = monome 3. 2;;

let rec puissance k = fun 0 -> 1 | n -> k * puissance k (n-1);;

let rec evalue p valeur = match p with
	| Somme (q,r) -> evalue q valeur + evalue r valeur
	| Difference (q,r) -> evalue q valeur - evalue r valeur
	| Produit (q,r) -> evalue q valeur * evalue r valeur
	| Puissance (q, n) -> puissance (evalue q valeur) n
	| Const a -> a
	| X -> valeur;;

evalue p 3;;


let rec keme liste = fun
| 0 -> let t::q = liste in t
| k -> let t::q = liste in keme q (k-1);;

let rec keme liste = fun
| 0 -> hd liste
| k -> keme (tl liste) (k-1);;

let renverse =
	let rec aux accu liste = match liste with
		| [] -> accu
		| t::q -> aux (t::accu) q
	in aux [];;

renverse [2; 3; 4];;
] -> failwith "Liste trop courte"
|[x] -> x
|t::q -> f t (reduce f q);;

reduce (prefix +) [2; 3; 4];;
reduce max [2; 3; 4];;

let reduce2 f l =
	let rec aux accu l = match l with
		|[] -> accu
		|t::q -> aux (f accu t) q
	in aux (hd l) (tl l);;

it_list ;;
list_it;;

(* Exercice 3 *)
let longueur_term =
	let rec aux accu l = match l with
	|[]->accu
	|_::q -> aux (accu+1) q
	in aux 0;;

let rec l = 0::1::l;;
(* Exercice 6 *)


let rec divise l l1 l2 = match l, l1, l2 with
	|[], l1, l2 -> l1, l2
 	|a::b, l1, l2 when list_length l mod 2=0 -> divise b (a::l1) l2
 	|a::b, l1, l2 when list_length l mod 2=1 -> divise b l1 (a::l2)
  ;;

  divise [4; 8; 90; 37; 79] [] [];;


let rec fusion l l1 l2 = match l, l1, l2 with
|l, [], [] -> rev l
|l, a::b, c::d when a<=c -> fusion (a::l) b (c::d)
|l, a::b, c::d when a>c -> fusion (c::l) (a::b) d
|l, [], c::d -> fusion (c::l) [] d
|l, a::b, [] -> fusion (a::l) b [];;


fusion [] [4; 37; 73] [4;37; 63];;

let rec tri_fusion l = match (divise l [] []) with
|l1, l2-> (fusion [] (tri_fusion l1) (tri_fusion l2 ))
|[], []-> l;;

tri_fusion  [2;1;35;7];;

let rec pol l = match l with
|[] ->0
|[a] -> int_of_string a
|[a;b;c] -> match a with  |+ -> int_of_string(b)+int_of_string(c)
									|- -> int_of_string(b)-int_of_string(c)
									|* -> int_of_string(b)*int_of_string(c)
									|/ -> int_of_string(b)/int_of_string(c)
|a::b::c -> pol b;;