```(**************************************************************************)
(*                                                                        *)
(*  Copyright (C) Jean-Christophe Filliatre                               *)
(*                                                                        *)
(*  This software is free software; you can redistribute it and/or        *)
(*  modify it under the terms of the GNU Library General Public           *)
(*  described in file LICENSE.                                            *)
(*                                                                        *)
(*  This software is distributed in the hope that it will be useful,      *)
(*  but WITHOUT ANY WARRANTY; without even the implied warranty of        *)
(*  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                  *)
(*                                                                        *)
(**************************************************************************)

(** Polynomials over an abstract ring.

This module implements polynomials with coefficients in an arbitrary
ring, as a functor. The resulting module also implements a ring, and
thus multiple applications yield polynomials in several variables.
*)

module type Ring = sig
type t
val zero : t
val one : t
val add : t -> t -> t
val neg : t -> t
val mul : t -> t -> t
val equal : t -> t -> bool
val print : Format.formatter -> t -> unit
end

module type Polynomial = sig
type r
(** The type of the coefficients (a ring); in the following,
we note [r0] and [r1] the zero and one values of this ring. *)

include Ring
(** The ring of polynomials *)
(** Ring constants and operations over the polynomials. *)

val monomial : r -> int -> t
(** [monomial r n] creates a monomial of coefficient [r] and degree [n]. *)

val create: (r * int) list -> t

val var : t
(** The variable; same as [monomial r1 1]. *)

val sub : t -> t -> t
(** for convenience *)

val deg : t -> int
(** The degree of a polynomial; returns [-1] if the polynomial is zero. *)
val leading_coeff : t -> r
(** Leading coefficient; returns [r0] if the polynomial is zero. *)

type monomial = private { coef : r; degree : int }
val view : t -> monomial list
(** A polynomial as a list of monomials, in decreasing order of degrees,
with non-zero coefficients. *)

val eval : t -> r -> r
(** [eval p v] evaluates [p(v)] *)

end

module Make(X : Ring) : Polynomial with type r = X.t

(** Polynomials over a field *)

module type Field = sig
include Ring
val div : t -> t -> t
end

module type PolynomialF = sig
include Polynomial

val division : t -> t -> t * t
(** [division u v] divides [u] by [v], i.e. returns two polynomials
[q,r] such that [u = qv + r] and [deg r < deg v].
Raises [Division_by_zero] if [v=0]. *)

end

module MakeF(X : Field) : PolynomialF with type r = X.t

```

This document was generated using caml2html