polynome.mli
(* la structure d'anneau *) module type ANNEAU = sig type t (* type des éléments de l'anneau *) val zéro : t val unité : t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit end ;; (* la structure d'anneau sur des valeurs de type t *) module type POLYNOME = sig type c (* type des coefficients *) type t (* type des polynômes *) val zéro : t val unité : t (* unité pour le produit des polymôme. Superflue, car c'est un cas particulier de monôme, mais cela permet à la structure de polynôme d'être une superstructure de celles des anneaux *) val monôme : c -> int -> t (* monôme a k retourne le monôme a X^k *) val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit val eval : t -> c -> c end ;; (* Le fonction qui étant donné une structure d'anneau retourne une structure de polynôme. Il faut faire attention à réexporter le types des coefficients de façon partiellement abstraite afin que les opérations sur les coefficients des polynômes puissent être manipulés de l'extérieur *) module Make (A : ANNEAU) : (POLYNOME with type c = A.t) ;;
polynome.ml
(* la structure d'anneau *) module type ANNEAU = sig type t val zéro : t val unité : t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit end ;; (* la structure d'anneau sur des valeurs de type t *) module type POLYNOME = sig type c type t val zéro : t val unité : t val monôme : c -> int -> t val plus : t -> t -> t val mult : t -> t -> t val equal : t -> t -> bool val print : t -> unit val eval : t -> c -> c end ;; module Make (A : ANNEAU) = struct type c = A.t (* un monome est un coeficient et une puissance *) type monôme = (c * int) (* un polynome 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 = monôme list (* pour que la représentation soit canonique, on élimine aussi les coeficients nuls, en particulier le monome nul est la liste vide *) let zéro = [] (* on peut donc (grâce à l'invariant utiliser l'égalité générique *) let rec equal p1 p2 = match p1, p2 with | [],[] -> true | (a1, k1)::q1, (a2, k2)::q2 -> k1 = k2 && A.equal a1 a2 && equal q1 q2 | _ -> false (* création d'un monôme *) let monôme a k = if k < 0 then failwith "monôme: exposant négatif" else if A.equal a A.zéro then [] else [a, k] (* un cas particulier l'unité *) let unité = [A.unité, 0] (* attention à respecter l'invariant et ordonner les monômes *) let rec plus u v = match u, v with (x1, k1)::r1 as p1, ((x2, k2)::r2 as p2) -> if k1 < k2 then (x1, k1):: (plus r1 p2) else if k1 = k2 then let x = A.plus x1 x2 in if A.equal x A.zéro then plus r1 r2 else (A.plus x1 x2, k1):: (plus r1 r2) else (x2, k2):: (plus p1 r2) | [], _ -> v | _ , [] -> u (* on pourrait faire beaucoup mieux pour éviter de recalculer les puissances de $k$, soit directement, soit en utilisant une mémo-fonction *) let rec fois (a, k) = (* on suppose a <> zéro *) function | [] -> [] | (a1, k1)::q -> let a2 = A.mult a a1 in if A.equal a2 A.zéro then fois (a,k) q else (a2, k + k1) :: fois (a,k) q let mult p = List.fold_left (fun r m -> plus r (fois m p)) zéro (* une impression grossière *) let print p = List.iter (fun (a,k) -> Printf.printf "+ ("; A.print a; Printf.printf ") X^%d " k) p (* Puissance c^k, c un coefficient, k un entier >= 0. Par dichotomie. *) let rec puis c = 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 c = match List.rev p with | [] -> A.zéro | (h::t) -> let (* Réduire deux monômes en un. NB: on a k >= l. *) dmeu (a, k) (b, l) = A.plus (A.mult (puis c (k-l)) a) b, l in let a, k = List.fold_left dmeu h t in A.mult (puis c k) a end ;;