(* Polynômes à une variable, avec coefficients dans un anneau quelconque

   Voir d'abord l'exercice 2.45. *)

module type Ring = sig
  type t
  val zero : t
  val one : t
  val add : t -> t -> t
  val mul : t -> t -> t
  val equal : t -> t -> bool
end

module Poly(R: Ring) : sig

  include Ring

  val create: (R.t * int) list -> t

  val eval: t -> R.t -> R.t

end = struct

  type monomial = { coef : R.t; degree : int }   (* coef <> R.zero *)
  type t = monomial list          (* triée par degrés décroissants *)

  let zero = []

  let one = [ { coef = R.one; degree = 0 } ]

  (* construit un monôme, en assurant que le coefficient n'est pas nul *)
  let monomial c d =
    if R.equal c R.zero then [] else [{ coef = c; degree = d }]

  (* faire la somme de deux polynômes revient à fusionner deux listes triées *)
  let rec add p1 p2 = match p1, p2 with
    | [], _ ->
        p2
    | _, [] ->
        p1
    | m1 :: r1, m2 :: r2 ->
        if m1.degree > m2.degree then
          m1 :: add r1 p2
        else if m1.degree < m2.degree then
          m2 :: add p1 r2
        else
          let c = R.add m1.coef m2.coef in
          if R.equal c R.zero then
            add r1 r2
          else
            { coef = c; degree = m1.degree } :: add r1 r2

  (* pour assurer que les monômes sont bien triés par degrés décroissants,
     on les ajoute un par un avec la fonction add *)
  let create ml =
    List.fold_left (fun p (c, d) -> add (monomial c d) p) zero ml

  let mul p1 p2 =
    (* multiplication par un monôme *)
    let mul_monomial m p =
      List.fold_right
        (fun m' acc ->
           let c = R.mul m.coef m'.coef in
           if R.equal c R.zero then acc
           else { coef = c; degree = m.degree + m'.degree } :: acc)
        p []
    in
    List.fold_left (fun p m -> add (mul_monomial m p2) p) zero p1

  (* exponentiation efficace *)
  let rec power x n =
    if n = 0 then
      R.one
    else
      let y = power x (n / 2) in
      if n mod 2 = 0 then R.mul y y else R.mul x (R.mul y y)

  (* l'évaluation parcourt la liste en partant des degrés les plus faibles *)
  let eval p x =
    (* v = valeur courante, xk = x^k *)
    let rec loop v k xk = function
      | [] -> v
      | { coef = c; degree = d } :: l ->
          assert (d >= k);
          let xd = R.mul xk (power x (d - k)) in
          loop (R.add v (R.mul c xd)) d xd l
    in
    loop R.zero 0 R.one (List.rev p)

  (* la représentation triée permet une comparaison efficace *)
  let rec equal p1 p2 = match p1, p2 with
    | [], [] ->
        true
    | [], _ | _, [] ->
        false
    | m1 :: r1, m2 :: r2 ->
        m1.degree = m2.degree && R.equal m1.coef m2.coef && equal r1 r2

end


(* Test *)

module Int : Ring with type t = int = struct
  type t = int
  let zero  = 0
  let one = 1
  let add = ( + )
  let mul = ( * )
  let equal = ( = )
end

module P = Poly(Int)

let p = P.create [1,0; 1,2; 1,4]
let q = P.create [1,1]
let () = assert (P.eval (P.mul p q) 2 = 42)

This document was generated using caml2html