smol 0.0.1 (latest) · OCaml Package

Polynomials with coefficients in a semiring, which forms a semiring

Parameters

module K : Algebra.Semiring_S

Signature

type t = K.t p

val zero : 'a p

The zero polynomial

val is_zero : t -> bool

Check if the given polynomial is zero

val one : t

The unit polynomial

val of_scalar : K.t -> t

val to_scalar : t -> K.t

raises [Polynomial_is_not_scalar]
if the given polynomial is not a scalar

val to_scalar_opt : t -> K.t option

val of_literal : Literal.t -> t

The "variable" polynomial

val of_monomial : Monomial.Make(Literal).t -> t

Builds a polynomial with a single monomial of coefficient K.one

val singleton : Monomial.Make(Literal).t -> K.t -> t

Builds a polynomial with a single monomial multiplied by a coefficient

val flatten : t p -> t

Kxx ≡ Kx

val get_support : t -> Literal.t list

Returns the sorted list of variables occuring in the object

val equal : t -> t -> bool

Equality between polynomials. Assuming monomials only contain positive exponents, and the polynomials do not contain zero coefficients, the polynomial representation is unique, so equality is the equality of the coefficients for each of their monomial.

val deg : Literal.t -> t -> int

Returns the maximum degree of the given variable in the given polynomial. Returns a negative integer if the polynomial is zero.

val add : t -> t -> t

Adds two polynomials

val mul_scalar : K.t -> t -> t

Multiplies a polynomial by a scalar

val mul : t -> t -> t

Polynomial multiplication

val leading_coef : Literal.t -> t -> t * int

Returns the leading coefficient of p in the variable x, with the degree of x

val apply_raw : 
  (module Algebra.Mul_Monoid_S with type t = 'a) ->
  (module Algebra.Semiring_S with type t = 'b) ->
  (K.t -> 'a -> 'b) ->
  'a Map.Make(Literal).t ->
  t ->
  'b p

Partial application for polynomials. apply_raw A B op v p substitutes the literals in v with their mappings in p. op describes a multiplicative operation between K.t and A.t which results in B.t, it is used to compute the intermediate coefficients of the monomials.

val apply : 
  (module Algebra.Semiring_S with type t = 'a) ->
  (K.t -> 'a -> 'a) ->
  'a Map.Make(Literal).t ->
  t ->
  'a p

Partial application for polynomials. apply A is equivalent to apply_raw A A.

val eval : K.t Map.Make(Literal).t -> t -> t

Replace literals with values in K.t. Equivalent to apply (module K) K.mul

val substitution : t Map.Make(Literal).t -> t -> t

substitution p x q replaces variables with polynomials in p

val apply_at_0 : t -> K.t

Extract the constant value of the given polynomial

val deriv : Literal.t -> t -> (int * K.t) p

Derivation of p wrt var

val to_string : t -> string

Conversion to printable strings

module Infix : sig ... end

Prefix and infix operators

Mapping functions Note: setting K.zero as a coefficient for a monomial is equivalent to removing its binding in the map.

val map : ('a -> K.t) -> 'a p -> t

val mapi : (Monomial.Make(Literal).t -> 'a -> K.t) -> 'a p -> t

val merge : 
  (Monomial.Make(Literal).t -> 'a option -> 'b option -> K.t) ->
  'a p ->
  'b p ->
  t

val mem : Monomial.Make(Literal).t -> 'a p -> bool

val set_coef : Monomial.Make(Literal).t -> K.t -> t -> t

val update : Monomial.Make(Literal).t -> (K.t -> K.t) -> t -> t

val remove : Monomial.Make(Literal).t -> 'a p -> 'a p

val union : (Monomial.Make(Literal).t -> K.t -> K.t -> K.t) -> t -> t -> t

val compare : ('a -> 'a -> int) -> 'a p -> 'a p -> int

val iter : (Monomial.Make(Literal).t -> 'a -> unit) -> 'a p -> unit

val fold : (Monomial.Make(Literal).t -> 'a -> 'b -> 'b) -> 'a p -> 'b -> 'b

val for_all : (Monomial.Make(Literal).t -> 'a -> bool) -> 'a p -> bool

val exists : (Monomial.Make(Literal).t -> 'a -> bool) -> 'a p -> bool

val filter : (Monomial.Make(Literal).t -> 'a -> bool) -> 'a p -> 'a p

val partition : (Monomial.Make(Literal).t -> 'a -> bool) -> 'a p -> 'a p * 'a p

val cardinal : 'a p -> int

val bindings : 'a p -> (Monomial.Make(Literal).t * 'a) list

val get_coef : Monomial.Make(Literal).t -> t -> K.t

val to_seq : 'a p -> (Monomial.Make(Literal).t * 'a) Seq.t

val add_seq : (Monomial.Make(Literal).t * K.t) Seq.t -> t -> t

val of_seq : (Monomial.Make(Literal).t * K.t) Seq.t -> t

package smol

Parameters

Signature