module type VAR = sig val name : string end module Make (A : ANNEAU) (X : VAR) = struct type c = A.t (* un monôme est un coeficient et une puissance *) type monome = { coef : c; power : int } (* un polynôme est une liste de monomes triés par rapport au puissance *) (* il est essentiel de préserver cet invaraint dans le code ci-dessous *) type t = monome list (* pour que la représentation soit canonique, on élimine aussi les coeficients nuls, en particulier le monome nul est la liste vide *) let zero = [] (* on peut donc (grâce à l'invariant utiliser l'égalité générique *) let rec equal p1 p2 = match p1, p2 with | [],[] -> true | m1::q1, m2::q2 -> m1.power = m2.power && A.equal m1.coef m2.coef && equal q1 q2 | _ -> false (* création d'un monôme *) let monome a k = if k < 0 then failwith "monome: exposant négatif" else if A.equal a A.zero then [] else [ { coef = a; power = k }] (* un cas particulier l'unité *) let unit = [ { coef = A.unit; power = 0 } ] (* attention à respecter l'invariant et ordonner les monômes *) let rec plus u v = match u, v with (m1::r1 as p1), (m2::r2 as p2) -> if m1.power < m2.power then m1 :: (plus r1 p2) else if m1.power > m2.power then m2 :: (plus p1 r2) else (*/ assert m1.power = m2.power /*) let c = A.plus m1.coef m2.coef in if A.equal c A.zero then plus r1 r2 else {coef = c; power = m1.power } :: (plus r1 r2) | [], _ -> v | _ , [] -> u (* produit d'un monôme par un polynôme *) (* on pourrait faire beaucoup mieux pour éviter de recalculer les puissances de k, soit directement, soit en utilisant une mémo-fonction *) let rec mult_monome m p = (* on suppose que m est non nul, i.e.: *) (*/ assert not (A.equal m A.zero) /*) match p with | [] -> [] | m'::p' -> let c = A.mult m.coef m'.coef in (* Attention l'anneau n'est pas forcément intègre, donc il se peut que c soit nul, alors que m.coef et m'.coef sont toujours non nul, le premier par hypothèse, le second par construction *) let p'' = mult_monome m p' in if A.equal c A.zero then p'' else { coef = c; power = m.power + m.power} :: p'' (* on pourrait écrire : ``mult_monome (A.symm A.unit) p'' *) let symm p = List.map (function m -> { m with coef = A.symm m.coef }) p let mult p = List.fold_left (fun r m -> plus r (mult_monome m p)) zero (* une impression grossière *) let string_monome m = if m.power = 0 then A.tostring m.coef else if A.equal A.zero m.coef then "0" else let string_k = if m.power = 1 then X.name else String.concat "^" [ X.name; string_of_int m.power] in if A.equal A.unit m.coef then string_k else (A.tostring m.coef)^string_k let tostring p = if p = [] then "0" else "(" ^ (String.concat " + " (List.map string_monome p)) ^ ")" let rec puis c = (* Puissance c^k, c un coefficient, k un entier >= 0. Par dichotomie. *) function | 0 -> A.unit | 1 -> c | k -> let l = puis c (k lsr 1) in let l2 = A.mult l l in if k land 1 = 0 then l2 else A.mult c l2 let eval p x = (* eval_div lower p evalue le polynome p/X^lower. Ici aussi on pourrait tabuler le calcul des puissances de X *) let rec eval_div lower = function [] -> A.zero | m :: q -> (*/assert pow <= m.power *) A.mult (puis x (m.power - lower)) (A.plus m.coef (eval_div m.power q)) in eval_div 0 p end ;;