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