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