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

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) = struct

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

  (* 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) [] ml

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

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,1; 1,3; 1,5]
let () = assert (P.eval p 2 = 42)

This document was generated using caml2html